I AM ON A FLIGHT to Oslo, a city I know nothing about, except for this: It is in Norway, which is a Nordic country, which must mean that everyone there is eating New Nordic Cuisine. The city I come from, New York, is gripped by such cuisine, the food intelligentsia entranced by extensive tasting menus that feature strong dark breads, meat smoked over hay, and other ancient fare made modern.

The young woman seated next to me is the first Norwegian I have ever met. Long ago, decades before I became a restaurant critic, I was a sportswriter who spent countless hours in National Hockey League dressing rooms, but I never met any Norwegians back then, only Swedes named Anders and Ulfie. I ask her what Oslo restaurants she can recommend.

She practically claps her hands in joy at my good fortune, because I am landing in mid-September. She explains that this is when the lambs come down from the hills and are transformed into the national dish—lamb, potato, and cabbage stew, brimming with tasty lamb fat. She also raves about cod with potatoes and meatballs with potatoes.

I blanch. This does not sound like New Nordic Cuisine, which is rather refined. Her favorites sound as old as Odin or Thor, the hammer-fisted gods of Norse lore. I ask her if she is an admirer of New Nordic Cuisine. She’s never heard of it.

The traditional food of Norway is based on stews, roots, rye, and other stolid fare. It is often about preservation, offering, at its extremes, such esoteric dishes as salted, smoked, and dried sheep’s head and air-dried lutefisk. This is how the ancient Norwegians ate. Very little land was suitable for farming, and the country had no aristocratic class to create a fashionable culinary tradition.

New Nordic is the result of a dining trend made famous by Danish chef René Redzepi at Noma in Copenhagen. He served small portions of inventive food prepared with local products, essentially creating a modern cuisine. Today it is seen worldwide, characterized by small restaurants with chefs from Denmark, Finland, Iceland, Norway, or Sweden preparing food using house-made vinegars, locally produced yogurts, and foraged seaweed and berries. These chefs—mostly men, and a very few women—tend to work alone, or with tiny staffs, assembling multiple-course meals that emphasize seasonal, organic, and sustainable ingredients.

I disembark from my flight wondering if I’ll end up doing more exploring than eating in my quest for New Nordic Cuisine. I fear this style of dining might not be the first option on every hungry Norwegian’s mind.

MY HOTEL IS located at the far end of a tiny island in the harbor of downtown Oslo, reached by a short bridge from the mainland. Called The Thief, the hotel is part of a flashy development of condos, businesses, restaurants, and bars, mostly constructed of chrome, glass, and dark metal. Docked next to the hotel is the Royal Yacht of Norway, owned by the king. I didn’t even know Norway had a king. Given that it’s a social democracy—pretty much a welfare state—this seems a little odd.

The desk clerk explains that my room isn’t quite ready and kindly sends me up to the breakfast buffet, where a cook prepares fresh hollandaise to order for eggs Benedict. There is also a genius invention called mustard salami, wherein the meat is encrusted with mustard, no additional French’s needed. Neither of this is New Nordic, especially not the salami, which appears to be New Hebrew Cuisine.

My room has a balcony overlooking Oslo harbor, and the sun is so bright—sunshine in Scandinavia in September!—I have to squint to see the nearest fjord. Almost every tourist who visits Norway sets off for the magnificent northern inlets that cut through towering mountains and serve as centerpieces on Norwegian travel posters. Right in front of me are my own fjords, modest ones that surround squat islands, but fjords nonetheless.

“To dine in the New Nordic restaurants of Oslo is to realize the city is experiencing the start of a culinary uplifting.”

 A message awaits me. Christian Koblizek, an Austrian working in the local film industry, has received an email from a friend of mine and offers to meet me outside the hotel with his daughter, son, and dog. He says we will stroll to Mathallen Oslo, a new food hall I’m told is the first ever in Norway.

It is a 45-minute trek along streets that spin off in awkward directions. Oslo is not laid out in a grid, and soon I am completely turned around. Just before reaching the food hall, we amble along the narrow, bucolic Aker River, which cuts through the city.

Mathallen is the centerpiece of a relatively new project called Vulkan, which transformed an industrial and supposedly once dangerous, slumlike section of Oslo into a cultural and recreational showplace. Oslo today is so polished it’s hard to believe it ever had slums. A few remnants of the seedy, graffiti-marked old area, kept around for charm, look to me like nothing more threatening than the old Lower East Side of New York City.

The food hall, built on the bones of an iron foundry, is modest in size but filled with appealing shops, restaurants, and food stands. There I have my first and best traditional Norwegian dish, a creamy soup flecked with salmon, cod, and turbot. The Koblizek family happily orders fish and chips, fresh and good, although they are accompanied by a pea puree that might well have been used to caulk Viking warships.

Walking back to my hotel, a long march for me but effortless for my friends and their dog, we stop at Taco República, located on Torggata Street, once filled with small, immigrant-run shops but now gentrifying rapidly. Easily the best of the tacos is the barbacoa, made with that famous lamb. Don’t be surprised if people tell you that the new national dish of Norway is tacos. They are everywhere.

Later in my trip, I make another visit to the food hall, this time with Sverre Landmark, a Norwegian who works for the firm that developed the Vulkan area. He takes me for coffee at Solberg & Hansen, where I first decline a tasting, so pale and insipid are the roasted beans on display. Then I give in and am astounded by the fragrance. Every country has its own way of processing coffee, and Norway is entranced by delicacy.

Landmark takes me up a flight of stairs to a restaurant called Hitchhiker, supposedly selling Oslo street food, even though I never see any street food while walking the streets. There I have one of my favorite dishes, locally caught bluefin tuna, uncooked and sliced thin, for dipping in a butter-soy sauce. This is the first dish I eat in Oslo that I think might qualify as New Nordic Cuisine. To my knowledge, Norwegians of yore weren’t connoisseurs of raw fish.

And yes, I taste that famous lamb-and-cabbage stew. Landmark entices one of the cooks who works in the food hall to prepare it for us, after I complain that I haven’t been able to find it in a restaurant. It is predictably robust, to be kind. It provides all the cabbage a man might require while in Oslo.

But there is more to Oslo than its new food hall. One day, I join Einar Kleppe Holthe, 2007 barista champion of Norway and now an entrepreneur, for a driving tour of the city.

Our first stop is the Vingen Bar, which he operates in the privately owned Astrup Fearnley Museum of Modern Art, just a few steps from my hotel. The museum is invariably closed whenever I try to visit, but the café and bar, with friendlier hours, has a private entrance hidden around back. It offers thoughtfully sourced coffee and outdoor seating with sweeping views of the harbor and the horizon. On a clear day, it should not be missed.

Holthe drops me off at the Botanical Gardens, which I’ve asked to visit. The greenery has already faded, but I don’t mind, since my real destination is the café, which somewhat famously makes sourdough pastries. They sound fascinating, but they’re as bitter as they are sweet—a terrible combination. When I complain to the café counterman, he tells me with a smile that I should blame the Swedes, who apparently invented the dreadful things. Norwegians love to make fun of Swedes, and sourdough pastries provide a perfect opportunity.

NOTHING I'VE EATEN thus far, bluefin excepted, is furthering my mission of finding New Nordic Cuisine. So I start assembling a list of local restaurants that seem to qualify. I am minimally aided by the Internet, which has little information on the subject, and far better served by the well-informed food and beverage staff of the Thief Hotel. I uncover five spots that appear to offer the best and most original food of a rapidly modernizing city.

My first stop is Kontrast, located near the Mathallen food hall, which seems to be trying too hard to live up to its new Michelin star. The decor is stark, an open kitchen and exposed overhead pipes. The hard-edged room is astonishingly quiet—barely a sound from the hushed kitchen staff or the whispering guests, who seem in awe. Finally: an amuse-bouche of juniper-marinated duck breast with a foie gras crisp. It’s without a doubt New Nordic, nothing like traditional local food. Scallops are slightly salted but delicate, fresh, simple—another New Nordic success. Bread, made from spelt and rye flour, is glorious. (Whenever you’re in a New Nordic restaurant and the chef sends out warm bread with soft butter, you might be inclined to eat little else.) Then come mistakes: Piedmont truffles, a luxurious touch, paired with too-hard cured egg and dried-up miso-soy-mushroom sauce. Reindeer is tasty but decidedly French, a sauce binding the multiple elements on the plate. Classification: Nervous New Nordic Cuisine.

Pjoltergeist is the oddest restaurant in Oslo, maybe anywhere. It’s cramped and loud. I stash my overcoat on a cardboard box of Finnish vodka stowed on a windowsill, then take a seat at an overcrowded counter. After the first three courses—pork cracklings, spicy gazpacho, and Japanese octopus balls—I sit befuddled. Then comes hacked-up bluefin tuna on a blob of rice. Any sushi chef who made this mess would have little choice but to commit ritual suicide. Suddenly, a turnaround. Grilled turbot ribs with black garlic glaze, wonderfully savory. Tacos with sweetbreads. Côte de boeuf, a total surprise—my first beef dish in Oslo and a lavish addition to a moderately priced tasting menu. A restaurant unlike any other, almost fatally peculiar. Classification: Stoner New Nordic Cuisine.

“When I compare the New Nordic Cuisine of Norway with that of New York City, or with that of Noma, I am ashamed of my initial reaction.”

The Thief Hotel’s gourmet restaurant, Fru K, specializes in seafood and little else. Complex dishes, refined and innovative, with lots of emulsions, sprouts, and marinated veggies. Grilled and pickled leeks with mussel sauce; local king crab, soft and succulent, in a crab emulsion; and my favorite, perhaps because it’s the minimally manipulated local fish that I haven’t been able to find elsewhere: wild turbot, firm and fresh, sparkling with anchovy butter. Classification: Pristine New Nordic Cuisine.

Most difficult to get into is Kolanialen, a paradigm of a small restaurant, the kind to be cherished wherever it exists. Its neighborhood is unpolished—unusual in Oslo—with graffiti scarring a few nearby storefronts. It’s the perfect first stop for any American visiting Oslo. The ambience is very Brooklyn, with Edison bulbs, white tile, small tables, hard chairs, and a huge portrait of a sultry woman reading the New York Post.

The chef, Jay Boyle, from Australia, cooks unfussy, comforting food using superb ingredients. He’s a master of supercharged umami flavors. I eat slightly pickled pumpkin strands atop mushrooms in chicken stock, silken beef cheeks with creamy celeriac, and homemade sourdough bread with salted local butter. Dessert is a puffball of honey and cream, the honey chosen by Boyle after sampling eight kinds made by an urban beekeeper. Kolanialen isn’t like any other New Nordic restaurant I’ve visited, so homey and sweet I might be the only person who believes it qualifies as one. It’s certainly different from everywhere else I’ve eaten in Oslo. Classification: Mom’s New Nordic Cuisine.

Bokbacka serves my best meal of 2016, brilliant and flawless. Luxurious counter seating on soft sheepskin, like Putin at his dacha. Swedish chef Simon Weinberg stands front and center, like a Japanese sushi chef. The meal begins with a miniature slushie, shaved ice with wildflower syrup. Then tiny veggies, including lichen resembling fried shredded wheat, served on an elephant foot bonsai. Silly, perhaps, but delightful. Mozzarella, tomato, olive oil sorbet—the chef’s caprese salad—so perfect I never ask what such ingredients are doing in Norway. A single langoustine, the fattest, sweetest, and most delicious of my lifetime, unparalleled. A bun made from sourdough starter inherited from the chef’s mother. King crab in fava bean porridge with shaved bone marrow. Smoked fish with a shot of aquavit, kind of a tipsy Jewish breakfast break. Brisket of lamb, in lamb bouillon, a gorgeous peasant’s dish. Dessert of blueberries and lemon-marzipan ice cream.

When I ask Weinberg if his restaurant is truly New Nordic, he replies, “The term confuses a lot of people. Nordic has always been very bold flavors, the food to keep people alive in the winter, and New Nordic restaurants are light and subtle. What I am making is my own cuisine.” Classification: Nonpareil New Nordic Cuisine, the best I’ve ever eaten.

When I compare the New Nordic Cuisine of Norway with that of New York City, or, for that matter, with that of Noma, I am ashamed of my initial reaction: I thought the Oslo restaurants were overly audacious and independent, not following the rules of New Nordic Cuisine.

Or perhaps I wasn’t used to them being so much more fun than the New Nordic restaurants of New York. Those tend to be more focused and predictable, rarely varying from the norm. To dine in the emerging New Nordic restaurants of Oslo is to realize that the city is experiencing the start of a noteworthy, perhaps even momentous, culinary uplifting. The city’s best restaurants are in the first flush of discovery, prone to mistakes but less tied to the rules, and much more giving. For someone like me, a city cannot demonstrate more excitement than that.

>>Next: Miami's Oldest Neighborhood is Turning Up the Heat