In seafood shacks, at gourmet tables, and especially during a stomach-defying live-fish auction, Reggie Nadelson discovers the true—and a new—Hawaii. It's 5 a.m. at Honolulu's fish auction, and I'm eyeballing a quivering Hawaiian opah, a pink and silver moonfish, round and flat as a plate. Nelson Aberilla, a quality-control manager at the auction, cuts the tail off a tuna, sticks in his hand, pulls out some flesh, squishes it in his fingers: Is it firm enough? Fatty enough? He offers me a fistful. I feel my passion for sashimi ebb. More glistening fish—ahi, mahimahi, snapper, marlin, some 100 pounds—are hauled in on steel palettes from the loading docks of Honolulu's Kewalo Basin, where fishermen deliver their catch around one in the morning. Over six days on three Hawaiian Islands I ate fish, most of it sold through the daily auction. I ate fish thick as meat in sandwiches at surfers' bars, sashimi so exquisite it was an erotic experience. I ate plain fish, fancy fish, faux fish—a Chinese vegetarian dish that tasted like old blankets. "Can I just have some fish and chips?" says my traveling companion, whom I call the Cynic. But then he's English. Fish is in many ways a metaphor for Hawaii. This is, after all, a state that consumes twice as much fish as any other in the States. Not that long ago Hawaii was a food hell of stale buffets and "continental" cuisine. On an island where you could smell the pineapple plantations, the hotels served canned pineapple from the mainland. Now it's in the feverish grip of an evolving cuisine and celebrity chefs obsessed with local produce. Menus detail the provenance of a Waimea tomato as if it were a Vermeer. In the late 1980s, chef Roy Yamaguchi first mixed things up: classical techniques, tropical ingredients. This was pretty seditious stuff. Now it's big business. There are currently 27 Roy's and counting across the country, including the original barn of a place in east Honolulu. Fed up with Hawaii's lousy food, a dozen or so innovative chefs joined Yamaguchi just over ten years ago to promote Hawaiian Regional Cuisine. Suddenly everyone was buying local. Suddenly local suppliers rose to the challenge and mesclun replaced iceberg lettuce. Inevitably in an island state, fish was on the front line. Great fish. Local fish. Fresh fish delivered to the restaurants daily. So driven are these chefs to get the best that, according to Brooks Takenaka, who runs the fish auction, suppliers grab a fabulous fish just to keep someone else from having it. Takenaka, a marine biologist, is tall, elegant and erudite, a Japanese Donald Sutherland. "Days when I'm the auctioneer," he says, "I get the guys working with me in a feeding frenzy." The whole state is in a feeding frenzy. Call it Hawaiian Regional, Pacific Rim, Post Fusion. This is food with panache, fun food, accessible food, food as playful as the pink parasol in your blue Hawaii cocktail, flamboyant as a sunset over Waikiki, postmodern as a Las Vegas resort, but with references to Asia, France, California, and always Hawaii. These days, though, the pineapple is a salsa, the guava in coulis, the macadamia nut in a crab cake. It's the perfect culinary metaphor for the islands: the lush landscape; the endless seas; the mixed ancestry of the inhabitants—Asian plantation workers, European entrepreneurs, American missionaries. In the middle of the Pacific, halfway between Los Angeles and Tokyo, Hawaii is an island melting pot served on a white-bread dream of paradise. And I loved it. I loved the food, I loved the fantastic menus that might have been written by a delirious surfer-dude chef confronting the big wave. At Sansei, a seafood and sushi restaurant in Honolulu, I dined on Kapalua "butterfry" rolls of fresh snapper, smoked salmon, and blue crab. Island vegetables were flash-fried to a crispy crust. I contemplated the Spam musubi (sticky rice and Spam), at $500 a jokey homage to what the locals call Hawaiian paté. But mostly I ate fish in Hawaii. Not that there wasn't plenty of meat and poultry, pasta and puddings, and how could I resist the macadamia-coconut-crusted lamb chops at Alan Wong's in Honolulu. It's Wong, looking like a Hong Kong movie star in a shirt printed with pineapples, who takes me to the fish auction at dawn. Afterward, over coffee, he talks about his background. As with so many of the new Hawaiian chefs, his Asian ancestry, classical training, laid-back American style, and humor and drive all go into his cooking. Born in Tokyo, he came to Hawaii at age five. His mother was Japanese; his father, Chinese; his stepfather, Filipino.Wong grew up here. He worked as a dishwasher, went to cooking school, then to New York, where he learned French techniques from André Soltner at the old—the real—Lutèce. "For years they used to say the best food in Hawaii was on the plane coming over," jokes Wong. "But immigrants brought food and style; the Chinese brought the wok, and there were the descendants of those who came to work the sugarcane and pineapple plantations: Japanese, Samoans, Laotians, Thai, Koreans." He orders another cup of coffee and continues, "When we got together in 1991 to promote Hawaiian Regional Cuisine, it meant fusion, Pacific Rim, East/West, depending on the chef's own background. We did French-style sauces with wasabi. I spent my first year trying to understand ingredients." Out of this came some of Wong's riffs on childhood dishes. "Everyone grew up eating loco moco—white rice, fried brown beef patty, an egg, brown gravy, fried onions," he says. "I reinvented it with quail's egg and foie gras." And I was crazy about Wong's gussied-up version of the poki ceviche made by fishermen, who cut up ahi into rough cubes and cure it with local rock salt. Wong calls his delicate ahi wonton balls on avocado Poki-Pines. That night we eat at Alan Wong's, in an unprepossessing office building near downtown Honolulu. Inside—on the enclosed lanai—diners on rattan chairs under cone-shaped lights chatter with anticipation. At the table next to ours a waiter delivers Da Bag, an exploding Kilauea of appetizers. The waiter slashes the huge foil bag. Fragrant steam rises up. Inside are succulent steamed Manila clams with shredded Kalua pig, shiitake mushrooms, spinach, chicken stock, and tomatoes. This is big food, theatrical food. Hot California rolls of baked Kona lobster mousse wrapped in nori with crab-avocado stuffing are one appetizer. Another is the "soup and sandwich"—the sandwich grilled cheese, Kalua pig, and foie gras. It sounds awful, but it works. "Remember, you have to cook with both feet on the ground," André Soltner told Wong. "Fusion can be confusion if done just for the sake of creativity." Wong pulls it off. A spicy hash of shrimp and pork is smeared on the opakapaka (pink snapper), which is then steamed before truffle butter is added. The combination is rich and spicy, salty and moist. Grilled opah—that plate-shaped fish I had been eyeballing at the morning auction—comes with shrimp kimchee fried rice. Seared yellowfin ahi, the meaty tuna, is served rare with spicy Asian slaw. Yellowfin and bigeye tuna are almost always known in Hawaii simply as ahi. At Chai's Island Bistro, fresh ahi is rolled in seaweed and served with a yellow-curry sauce and fresh mango salsa. Pineapple salsa dances with crab cakes, spicy frog's legs squat on linguine marinara, grilled mahimahi is spiced up with Thai red-curry sauce. Of all the Hawaiian fusion chefs, Chai Chaowasaree is the most flamboyant. He grew up in Bangkok, where his mother had a restaurant. A boy with a passion for ripe melons and perfectly fleshed fish, he shopped Bangkok's markets. In 1988 he opened his Singha Thai restaurant in Waikiki and in 1999, Chai's Island Bistro. The mirrored balls overhead spin in the Hawaiian sunlight. At noon the place is full of businessmen, including one in a half-pound gold Rolex. He's glued to his cell phone. A middle-aged couple in the corner, regulars it appears, are fueling an illicit romance with wok-seared lobster and scallops in spicy-chili ginger sauce. I order another cold Thai beer. And for dessert? Chai's Hawaiian chocolate pyramid. With Tahitian vanilla crème anglaise, this is a veritable anthropological dig, Polynesian-style. As at Alan Wong's, there is a menu of Hawaiian coffees. A list of fine Asian teas was also available, including the irresistibly described Monkey Picked Chinese Snow Oolong: "The monkey is specially trained to pick the tea from the high-elevated mountains and cliffs in Taiwan where humans can't reach." It is hard to believe that the Hawaiian Islands were once almost devoid of food. According to James Michener in his monumental Hawaii, when settlers first arrived from Bora-Bora around a.d. 800 there was no fruit, no coffee, pigs, or chickens, nothing except fish. Fish became not just necessary for survival but the stuff of fetish, myth, ritual, and taboo. Of all the fish that I ate in Hawaii, my favorite was moi, a tender-fleshed white fish weighing only a pound or two. It's almost entirely farmed now. It was once a royal fish and unavailable to mere proles like you, me, and the rest of the world. One afternoon on Oahu, near the ancient royal fishponds, I met Aunt Nettie (a.k.a Lynette Tiffany), a kahuna, or priestess, and the caretaker of an old estate. Ebullient and feisty, she offered a blessing, talked about "summoning the fish," and showed me "sacred" ponds where Hawaii royals bathed. Here the moi was harvested. In the rigid Hawaiian caste system—which lasted into the 19th century—women never ate with men, and a nonroyal who tasted moi faced a nasty death. "I love moi," says Hiroshi Fukui, the chef at L'Uraku, as he serves a moi carpaccio made with local ginger and peanut oil. It's clean, velvety, refined. Pan-seared fillet of moi is next, the edges of the fish crispy, the middle soft; it's served with kabayaki butter sauce dotted with onion-chive oil and pickled red cabbage. "You eat with your eyes first," adds Fukui, whose Euro-Japanese fusion balances both cuisines with a light hand. Fukui, with a round, boyish face, is diffident, shy, passionate. He had no formal training but worked in Tokyo kitchens to learn the trade. His astonishing fish dishes include an oven-baked crabmeat sandwich and luscious seared scallops that feel like huge South Sea pearls in your mouth. Our last course is moi again, this time en papillote. Steamed lightly in chili-pepper water, the fillet is served up in its silver-foil bag. What makes it so perfect is that the silver foil is placed on a slip of red foil on the white plate. This restaurant—the prettiest in town—has red-leather banquettes and a forest of painted umbrellas hanging upside down from the ceiling. It's as if David Hockney had come to town, was blinded by the scenery, and designed parasols to keep out the sun. In Hawaii, color is almost so tangible you can feel it. At Hanauma Bay later that day I saw scores of fantastic fish—yellow, green, and blue, red, pink, and gold, some with stripes or dots, jail fish and window-cleaner fish. In the protected cove snorkelers ducked in and out of the sea like grazing gannets. At Chef Mavro, which is currently lauded as Hawaii's gastronomic temple, the only color is in the food and the waiters' Hawaiian-print ties. The restaurant is in a simple whitewashed-stucco building, but then George Mavrothalassitis, chef Mavro, is a Frenchman of Greek descent. Here the linen is crisp, the dishes white, the crystal simple. The only ingredients are local, prepared subtly and unaggressively. The cooking style is classic. Even the menu is sleek and lean. Dishes are simple as well. This may be the best restaurant in the islands. The refined cooking could compete with that found anywhere. Keahole lobster comes with asparagus risotto, truffle oil, crustacean coulis. The Pacific oysters are served with lemongrass vichyssoise, watercress velouté, and salmon roe. The onaga medallions appear with sea-urchin foam and leek étuvée. And then there are the doughnuts! The Portuguese brought malasadas, their version of jelly doughnuts, to the Hawaiian Islands in the latter part of the 19th century. Chef Mavro surrounds his with a guava coulis and pineapple-coconut ice cream. Not far from the docks where workers from Asia once disembarked to work the pineapple and sugar plantations is Chinatown, which dates back to 1900, even earlier. The low-lying buildings still have their red roofs, and women sit outside shops selling herbal medicine and advertising acupuncture. Here, the morning after dining at Chef Mavro, I cheated in my affair with fish. I bought a gorgeous bronzed babe of a duck hanging in the window of Nam Fong on Mauna Kea Street. The Cynic and I picked at the crispy, meaty flesh and skin as we wandered through the markets. Green frogs croaked in plastic buckets, black crabs lay dormant in glass cases next to giant clams, pink and white shrimp, slabs of rosy salmon. At Saigon, a classic Vietnamese noodle shop on North King Street, I slurp up the thick, slick noodles floating in the steaming broth peppered with tiny shrimp. Two elderly Chinese men, their faces as wrinkled as wet walnuts, one barefoot, the other in a flat cap and suspenders, are downing soup and smoking. Behind them, an evil-looking white fish slides through a tank. The Chinese presence in Hawaii is huge. On Saturday at Legend Seafood Restaurant you feel that you could be in Hong Kong. Chinese families pack the vast room, and waitresses shove dim-sum carts among the tables. Kids clamor for more pork buns. We consume shrimp-and-chive dumplings, cuttlefish and shrimp balls. There's no fusion here, no pretension—just straightforward, delicious Chinese food. The owner brings us a "faux" fish from Legend's sister vegetarian restaurant. Can we tell it's tofu? Are you kidding? It looks like Styrofoam; it tastes like sponge. But the whole fat red snapper cooked with ginger and scallion is the real thing. The Cynic is in heaven. "No hanky-panky here," he says, referring to the more outlandish fusion dishes. "Real food," he announces and orders another Chinese beer. I drank beer with dim sum and wine with the fancy stuff. Some of the restaurants have terrific wine lists, especially Chef Mavro, where there are exquisitely chosen white Burgundies from France, Rieslings from Germany, Russian River Valley Chardonnay, even Malmsey Madeira. At The Lodge at Koele on Lanai there was a wonderful Bandol rosé. Champagne, especially full-bodied Champagne like Veuve Cliquot, seemed to go surprisingly well with the Hawaiian food. To tell the truth, though, in Hawaii what I really wanted were cocktails. Sunset time over Waikiki. I'm outdoors at the Halekulani Hotel, where I stayed. I'm sampling mai tais, frozen daiquiris, and the fabulous frozen lemonade, slushy, tart, sweet. Late at night, after dinner, I'm back for a nightcap—a stinger, maybe—as the Cynic and I sit out under the moon and stars. On a little platform between the pool and the sea a trio plays. A former Miss Hawaii does a sedate hula. No one is watching. The crowd is more intent on its food and drinks. In the tropical moonlight, Miss Hawaii sways to the trade winds like a stripper at a club where the patrons never look up. Hotel food, which used to be largely from the school of synchronized lid-lifting, has changed. And nowhere is that seen to better effect than here. At the Halekulani, La Mer is a glamorous room overlooking the ocean. It serves formal, ornate French food. Zagat gives it one of the highest rankings in Hawaii for abalone with lime and celery remoulade and sautéed scallops with basil and pine nuts on a bed of squid-ink linguine. Roasted scampi comes with macadamia nuts on a fennel compote. Up the road at Diamond Head, at the Kahala Mandarin Oriental, is Hoku's. The view is Technicolor, the waiters attentive but not fawning. The gigantic black tiger prawns, like all the best prawns, are fleshy, sweet, simple. The Cynic devours opah with truffled white-corn grits, sliced artichoke in a lobster reduction. He is crazy about it, ready to give up fish and chips. Most of all I admire Hoku's plateau de fruits de mer. It resembles a Christmas tree made of shaved ice and decorated with shellfish, oysters, clams, shrimp, slices of perfect sashimi. But for raw fish, it's Sushi Sasabune. The rice is fluffy and warm, the fish lush, firm, velvety, and tasting faintly of the sea. Sushi Sasabune, on a dreary Honolulu street, is one of the island's best-kept secrets. Celebrities beg for a table when they're in town. We arrive six minutes late for our reservation. The waiter grimaces. The place is a dive, six tables, a sushi bar. The sound system plays Charlie Parker's lacerating "Parker's Mood." The point here is to obey the chef, Seiji Kumagawa. Eat what he tells you to. They call him The Sushi Nazi. OMAKASE, or TRUST ME, the sign says. As the sushi is served, the same waiter, more acolyte than server, instructs us exactly how to eat it. This is normally the kind of thing that makes me want to ask for the ketchup. Kumagawa has been quoted as saying it takes three years to learn to cook rice properly (it's cooked every two hours so it's always soft, warm, and tender). Ten years to do the fish (all the membrane must be removed). Unlike most Hawaiian restaurants, here the fish comes through the Los Angeles fish market. The selection, we're told, is bigger, better than Honolulu's: red snapper from New Zealand; halibut from Boston; toro from Japan. The calamari stuffed with blue crab with a fluffy wasabi is exquisite; so are the hamachi and toro, the salmon roe, the blue-crab hand roll, the eel and omelette, the uni, which the chef calls "ocean ice cream." Even the Cynic, who thinks sushi is food someone forgot to cook, says, "It's subtle, coercive, seductive. It's the platonic ideal of fishness. If some of those fusion places were a Gothic novel, then this is a haiku." Still, by Sunday he is begging for meat. We head for the north shore of Oahu and the funky beach town of Haleiwa. Think California in the '60s. Even before eleven, when it opens, people are lined up outside Kua 'Aina. A surfer with a melanoma tan, no visible fat, and bleached eyes lounges on the porch of this burger joint. Inside are a few tables and old-fashioned pale-green wainscoting. We eat on the porch. My mahimahi sandwich with green chilis and cheese is tasty, but the Cynic's burger is, well, paradise. Along the coast, past some of the famous surfing beaches, food stands sell corn, watermelon, coconut, pineapple, white and pink shrimp, all the bounty of this tropical paradise. We head back to Honolulu and next morning take an early flight to Lanai. Inevitably, most of the great restaurants in Hawaii are in Honolulu, the capital, home to nearly a million people. The new cooking, though, has reached the other islands, and you won't go hungry on the Big Island (Mauna Lani's CanoeHouse and Bungalows, Daniel Thiebaut, Merriman's); Maui (Mama's Fish House and Humuhumunukunukuapua'a, named for the state fish); or Lanai. Up in the highlands of Lanai, a tiny island that was once a pineapple plantation, The Lodge at Koele is set in grounds that are more Scottish estate than tropical paradise. The Formal Dining Room, pink and gold, is lit up by the setting sun. The chef, Bradley J. Czajka, along with Abderrazak Chadli (the chef over at the Clubhouse at Manele Bay, Koele's sister hotel), produces a fish feast. The hamachi and ahi tartare is topped with jewel-like beads of Iranian and Californian caviar. The roasted moi is moist with bell-pepper oil. Then there's mustard-crusted salmon, pink as a fat little matron, on baby beet salad in lemon-dill butter sauce with chive-potato dumplings. By the time the Malaysian-style baked ono with lakysa sauce comes I'm reeling. I reel straight on into Hawaiian snapper on scallop-and-Portobello "cannelloni," dusted with fennel pollen, set among wilted spinach, red onions, pears, and a mushroom emulsion. My favorite course comes last. It's a spicy Moroccan-style tajine of fish. The clay pot with the hat-shaped cover holds blue-nose sea bass served with charmoula. I'm growing gills. Edwin Goto, the first chef at The Lodge at Koele, which opened in 1991, is now executive chef at Mauna Lani. By the time we arrive at our bungalow there, all I want is something simple. Goto produces a meal fit for the very rich patient who has recently overindulged. In the dining room of our spectacular bungalow (there are only five) we eat dinner, served by two butlers: a salad of baby greens with oranges; braised opakapaka, snapper cooked in mushroom broth flecked with vegetables and chive shoots. A row of candles flickers on the table. Cold Champagne bubbles alongside the warm coconut pudding cake. (Next time, when we have more room, chef Goto promises spiced-beef salad with wilted Asian greens, or his five-spiced duck with chili-vinegar sauce.) After dinner we wander through the bungalow. It's elegant, sleek, faintly Asian in design. There's lots of Japanese-style wood furnishings and huge sliding-glass doors. There are two bedrooms, immense bathrooms, and a living room that opens onto a private lanai and pool. At dawn the next morning I go for a swim as the sun is coming up over the surreally green golf course, and beyond it the blue Pacific. Nearby, in my private pond, a golden fish swims. From inside I hear the television. The Cynic rushes out to tell me the lead story is about worldwide fish shortages. If we're not careful, the oceans will soon be fished out. Never mind, he says, there have always been dire warnings. Quoting Hemingway's Old Man and the Sea, he pronounces portentously, "Fish I love you and respect you very much. But I will kill you dead before this day ends."