For most of the 1,100 years since Iceland was settled, the island's food had more to do with surviving the long, sunless winters than it did with making something that was remotely palatable.
In order to eat when the ground was frozen and the snow too thick to venture outside, fish was pickled in whey or smoked with a combination of hay and dung. Then there were rank foods like skata, or rotten skate, which would stink up clothes so badly diners would have to toss them out a afterward.
Throw in 500 years of Danish rule, which did little else but cause mass poverty and suppress traditions, and the occasional volcanic eruption that killed all crops and most livestock, and you have a culinary tradition that was so confused and inefficient it needed to be rebuilt from the ground up.
Fast-forward to 2009, when fine dining in Reykjavík consisted mostly of gimmicky tourist restaurants serving whale and puffin.
Then a restaurant called Dill opened and everything changed.
Aligned with the emerging New Nordic cuisine movement, it embraced traditional methods like wind-drying catfish and smoking lamb in dung, and reintroduced native barley, dulse, and blue mussels into the Icelandic diet.
Dill is still going strong, and this year it earned the country's first Michelin star, even though founding chef Gunnar Karl Gíslason has relocated to New York to run Noma cofounder Claus Meyer's Grand Central Station restaurant, Agern (which also boasts a Michelin star).
Gíslason still oversees a mini-empire of Reykjavík restaurants, including Dill, which is now headed by chef Ragnar Eiríksson in a building in the chic 101 neighborhood.
The space, with stone walls and beamed ceilings hung with drying fish, evokes a dark barn or fishing cottage, yet one where progressive seven-course menus are served with natural wines.
Eiríksson has also launched a series of regularly sold-out themed pop-ups called Matartíminn, held on uninhabited islands or focusing on open-fire cooking.
These days, you don't have to go very far for an excellent place to eat.
For example, climb the stairs to the floor above Dill and you'll discover Hverfisgata 12, an unmarked eatery and bar decorated like a carnival by set designer Hálfdán Pedersen, offering eclectic gourmet pizzas and small plates like fried duck eggs with coppa, cauliflower, Ísbúi cheese, and fennel.
Go one more flight up and there's a branch of Danish cult beer bar Mikkeller & Friends.
"Lately we've been seeing higher-end restaurants changing their concepts or even closing," Gíslason says. "More and more restaurants are focusing on casual, fun, and cheaper meals."
Old favorites like the famous hot dog stands (Baejarins Beztu Pylsur, to name one) and the lobster soup at Saegreifinn are still worth trying, but the all-around quality of eating in Reykjavík has improved considerably.
There's Oslo-level coffee at Reykjavík Roasters and bakeries like Sandholt and Brauð & Co that are experimenting with ancient grains, as well as 10 small restaurants in a new food hall in the former Hlemmur bus station.
"We obviously have a huge increase in the number of restaurants," says Olafur Ágústsson, who runs the always lively gastropub Sæmundur í Sparifötunum inside of Kex, a hostel in an old biscuit factory on the Reykjavík waterfront, which also produces its own line of craft beers.
"As a country boy, I am also really happy to see better restaurants opening in the countryside."
During the summer, catch a short flight or ferry to the tiny volcanic island of Heimaey off the south coast, where chef Gísli Matthías Auðunsson and his family run a seasonal restaurant called Slippurinn in an old shipyard machine workshop.
Wild herbs and seaweeds are foraged around the island, while he picks up fish next door at the market for dishes like whole cooked cod head and langoustines with sea truffles.
In the fishing village of Seyðisfjörður on the east coast, try Nord Austur, a sushi restaurant that's named after the direction of the wind and works with local fishermen.
Despite Reykjavík's raucous nightlife scene, up until 10 years ago it was impossible to find a decent drink. That has quickly changed, as a new fleet of colorful drinking dens, such as Geiri Smart and Slippbarinn, have opened.
In addition to internationally known vodka brands, bartenders are working with Icelandic microdistilleries to turn local flavors into their own spirits.
The Foss Distillery uses Icelandic birch to produce a liqueur and a schnapps, Björk and Birkir, respectively, while Eimverk Distillery makes a pot-distilled gin with botanicals like angelica root and creeping thyme and single-malt whiskeys with Icelandic barley.
"Drinking has become one of the national pastimes in Iceland," says Ólafur Örn Ólafsson, who recently opened the bar and live-music venue Rosenberg.
"Most people still do their binge drinking at home before going to bars, but more and more craft beer and cocktail bars are opening. For example, imported beer has lost most of its market share to locally brewed craft beers, most of which are well above mediocre."
Beer was prohibited until 1989, but has quickly rebounded, taking advantage of the country's pristine, glacier-fed water supply.
There are dozens of microbreweries around the country, from tiny Borg in Reykjavík, with its sheep-dung-smoked Imperial stout, which won the gold medal at this year's European Beer Star competition, to the rural Ölvisholt Brugghús, which runs tours of its farmhouse brewery in the south of the country.
Then there is Steðja microbrewery in West Iceland, which makes a beer with a whale testicle, butchered according to tradition and then salted and smoked with sheep dung.
What could be more Icelandic than that?