At Aljui Bay, on the west side of Waigeo, the oddest beast I've ever seen came crawling out of the dark in the weirdest place I've ever dived. The dive site, a shallow patch of muck, lay underneath the dock of a pearl farm, a far-flung place, to be sure, like a trading post out of a Conrad novel. A moonless night set the proper mood for poking about with dive lights. The first creature my scuba buddies illumined was a giant sea snail caught in the act of extruding a gelatinous string of Ping-Pong-ball-size eggs onto one of the dock's outer pylons. Just inside the first row of pillars, a fire urchin, the size and color of a jack-o-lantern, with short spines and what appeared to be feathers, lay cheek by jowl with a sea hare—a grandiosely proportioned sea slug, a regular Jabba the Hutt. Mesmerized, I watched a certain flatworm, trying to figure out how something flat could appear to be revolving like a barber's pole in two different directions, when suddenly I felt a prick and an electric jolt. While I'd been gaping at the worm, a battalion of urchins, the mobile kind with long, wicked spines, had crept up to see if I was edible. The bravest of the lot had pronged me in the ankle.

I kicked away in haste. About then I saw someone waving his light, a signal to come have a look. It was Erdmann, our go-to guy on the cruise for all the rare or hard-to-find stuff.

The nearly three-foot beastie had the face of a newborn puppy, and it moved with the contorting waddle of an antique wind-up toy, walking—yes, walking!—on the tips of its pectoral and pelvic fins. It was the walking shark, of course, which we had been looking for all along, not quite believing in it. The discovery of two new walking shark species in 2006 by a Conservation International expedition had made international news and had occasioned more than a few waggish SNL-inspired blogs: Walking shark? Candygram! This one performed for us under half a dozen dive lights, lurching over the rubble—right fins forward, push! Left fins forward, push!—like a patient undergoing painful physical therapy. It was amazing to watch, and we would have until we ran out of air, but at last, annoyed by the attention, it swam off quite briskly.

There's an evolutionary riddle for you: Why does the walking shark walk when, like any self-respecting elasmobranch, it can swim just fine when it chooses to and, in fact, it walks rather poorly?

The question stuck with me as we steamed south for Misool, where I had my own little Darwinian crisis. I've said that we were all advanced divers on this trip, but I was the least advanced, the one who saw everything last and used up his air supply first, and at a site near Misool's Wayalibatan Channel I was nearly naturally deselected for my lack of fitness. It happened at a spectacular wall called FantaSea, an enchanted forest of gorgonian sea fans waving in the five-knot current. As we had traveled south, the visibility had declined from incredible to merely very good, owing to nutrient-rich upwellings, and the density of fish had just gone crazy. These southern reefs were loud with life—the clickings and scrapings of claw and tooth like the din of cicadas—and visually furious, gouts of color flung and splattered.

On this dive, though, everyone was looking for pygmy sea horses, a Raja Ampat specialty. The creature is tiny—about the size of a grain of rice—and mimics perfectly the tint and the texture of its favorite hiding place, the screenlike grid of the gorgonian sea fan. To find the animalcule, you must comb through the leaves as if looking for fleas on a great shaggy dog. Even when your keen-eyed dive guide has found one for you, it's hard to see without a magnifying glass. Yet, with those anise-seed eyes, the blunt plumped muzzle, the cunningly nubbed pastel hide, it has its own curious charisma, equal to the whale's. So people said, anyway. I still hadn't seen one.

I was determined not to be shut out, so every time one of the guides rapped on his tank, I kicked like mad to get into viewing position—up, down, back, forth—until at last: Bingo! Excellent! Tiny! Cool! And then I noticed my Suunto dive computer flashing, warning me I was about to go into decompression mode—a big no-no, especially in a strong current. I also noticed I was nearly out of air. So I signaled to my group that I was heading up and began kicking for the surface. I spent my three-minute safety stop at a depth of 15 feet congratulating myself on having, almost definitely, seen a pygmy. When I broke the surface, the Citra Bidadari was nowhere in sight; the Zodiacs were elsewhere as well, and the current was still motoring me toward Antarctica and kicking up four-foot haystacks, which would make me nearly impossible to find. Fortunately, I had a signaling device—a bright-orange inflatable "sausage," for which I silently thanked Seacology's executive director, Duane Silverstein, and his pre-trip checklist. This I held above me at arm's length. It barely topped the waves. I yelled "Help!" a couple of times. That was dumb. Five minutes later, I dropped my weight belt, the first time I'd ever taken that drastic measure, and five minutes after that I began to think I'd really been forgotten, and what a long and lousy death I was going to die.

Of course, the able boatmen of the Citra Bidadari would never lose a customer. Twenty-one minutes after surfacing, I heard the growl of an outboard and soon saw my very good friend Dewey racing to the rescue. But in that interval of treading water, I'd had ample opportunity to hold up a mirror, as Sylvia Earle had asked, and see who I was and what I did best. I'm someone who expects the worst, is surprised by the best, and somehow survives to tell the story. So if the worst comes to pass—as I expect it will—and Raja Ampat is blasted to smithereens for frozen fish sticks, and the seas all die and all of us along with them, there's a certain shark in Aljui Bay that's ready to crawl up the beach and start the whole thing over again.