It was only 10am in the morning but the Ostabudin deli, a sleepy main shopping street in central Reykjavik, offered a taste of the day ahead.

There were five different types of goose available, including a pink-footed variety that summers among thyme and fennel; dark poultry-like strips of guillemot served with raspberry and champagne vinegar; salty carpaccio of curried horse fillet with rosemary; liquorice-flavoured cured lamb and hard Icelandic sheep's cheese.

We were just having tasters but it followed hot on the heels of a breakfast of skyr (pronounced skeer), Iceland's low-fat “secret recipe” skimmed-milk curd flavoured with blueberries and strawberries. A centuries-old breakfast staple in Iceland, skyr has a very rich taste and texture for such a low-calorie dairy product.

In preparation for the next course we fasted for 40 minutes or so with a peek in the city's sharp looking cathedral, where they were warming up the pristine silver pipes of the organ for a statesman's funeral and, for a brief magical moment, we had the place to ourselves.

The view from the tower, reached by a lift, slopes down to the chilly waters over the capital’s Lego-like red-roofed houses.

As a fishing port Reykjavik ranks only seventh in terms of tonnes of fish landed in Iceland. Domestically the fishing industry generates about 50 per cent of the nation’s visible export earnings and yields large amounts of redfish, herring, cod and haddock, plenty of which ends up on British plates. We’d have to wait for the first catch of the day at Saegreifinn, a strip-lit seafood shack on the other side of town.

First, on the way to a famous-in-Iceland hot-dog stand we dropped in at 12 Tonar, a neighbourly record store and popular haunt with local heroes Bjork and Sigur Ros. I took an espresso downstairs, courtesy of the owners, and listened to Icelandic folk music on big headphones. From there it was a short walk across town to Baejarins Beztu’s fast-food national institution.

I bailed on a hot dog, correctly anticipating that there was a lot of better food to come. It was, after all, still only 11am. Depending who you ask Baejarins Beztu owes its success to the rémoulade sauce, the mustard, the crispy fried onions, the ground lamb and pork filling or the crunchy casing. Presumably it’s not down to the raw onions, but then you never know. The stand, founded in 1937, has vintage wooden hot dog holders.

At Saegereifinn we hooked up with Agnar Sverrisson, Iceland's culinary chieftan and our “sat-nav” for the rest of the day. A former head chef at Raymond Blanc’s Le Manoir and, by his own admission, not the only chef to have had a run-in with Tom Aikens when they worked together at Pied a Terre, Sverrisson now captains Texture restaurant in London, but was home scouting for new produce and ideas to infuse his menu with Nordic nuances.

Squeezed shoulder to shoulder on upturned salted herring tanks we savoured hot lobster soup – yet another secret recipe - with Viking beer and rotten shark cut into pale gelatinous cubes. The shark had been buried beneath the ground by the sea for a year, where it sheds its acrid ammoniac fluids. “It’s toxic fresh, but a delicacy when processed,” said Sverrisson, encouragingly. The shark’s mild pong was followed by an intense salty cheese flavour rapidly muted by a chasing shot of brennivin, or Black Death, a potent Schnapps made from fermented potato pulp and the country’s preferred alcoholic tipple.

The shelves of a single open refrigerator were packed with bloody red mink whale kebabs, lobster and pepper skewers and packs of haddock chips, crispy codskin wafers and Icelandic seaweed. The stuffed sea lion on the wall was not on the menu.

Next, we stepped up a gear to the classy Humarhusid restaurant not far from the Prime Minister’s office in the centre of town. Housed in a low-slung sage coloured building from 1838 the elegant dining room has wooden floors, oil paintings on grey walls and oak tables beneath chandeliers. It was quiet.

Times recommends

• Travel advice: what to do if your flight is disrupted
• Top 10 unmissable events in 2010
• Seven spa breaks for January