I'll be going to Reykjavík in a few weeks. As usual for my job travels I'm trying also to enjoy the place, and in this case the cuisine.
I tried to have a look on wikipedia Reykjavìk page, but it doesn't even touch this subject!
So my question is: which is a very typical Icelandic food from Reykjavík that I MUST taste?
If you want to try Minke Whale and Puffin, you can get both of these in small portions at Tapas Barinn (The Tapas Bar), which serves them alongside more traditional Spanish tapas. You should also try the lobster soup at Sægreifinn, which come highly recommended (I'm not a big seafood fan but everyone I know who is and has tried it recommends it).
Harðfiskur (dried fish) and hákarl (putrefied shark) are both served (again in small portions) as part of the Icelandic Braveheart Breakfast at Café Loki opposite Halgrímskirkja, the big church you can see from almost the whole city. They are served with some delicious rye bread and a shot of Brennivín - hair of the dog if you've had a hard night. Their menu also includes other traditional Icelandic food.
The BSÍ Bus Terminal (where your bus from the Airport will arrive in town) has a café that serves Svið - boiled sheep's head. You can also buy a lot of traditional food in the supermarkets.
And if you really want to go to town, figuratively speaking, you should visit during the month of Þorri and attend a Þorrablót, where they serve everything from ram's testicles to blood pudding, and more.
And finally, the far more accessible Skyr, the local yoghurt (debates still rage about whether it IS actually a yoghurt) comes in many flavours and can be bought from any supermarket in individual portions.
I would recommend:
If you are very adventurous you could also try things like putrescent shark meat (Hákarl), but don't expect it to taste good.
You should also take a look at the Wikipedia's Icelandic cuisine page.
If you want to taste some of the freshest fish on the planet, then head straight for Icelandic Fish & Chips. They have different fish every day depending on the catch of the morning, examples being Cod, Ling and Wolf fish. You won't find fish n chips like this in the UK - an icelandic must.
Address:
Icelandic Fish & Chips, Tryggvagötu 8, 101 Reykjavík
Additionally
If you are really after a true Icelandic delicacy, you might like to try skata which is putrefied skate, the smell is akin to strong smelling cheese.
It is mostly eaten once a year on December 23rd to celebrate Thorláksmessa - Mass of St. Thorlák, patron saint of Iceland.
More information about this strange smelling delicacy can be read here
Gamla Vínhúsið at Klapparstíg 38 in Reykjavík serves delicious Mink Whale. Prices are very reasonable for the area and they have a mix of local and generic dishes. Here is the whale steak with pepper sauce:
There is one desert Gamla is famous for too which was described to me as like Yogurt but not yogurt. I have no idea what either taste like because I am allergic to dairy products but I was told it is unique to Iceland.
If you walk down the major streets in downtown Reykjavík you will see quite a few restaurants. Most serve international fare because I suppose that is what people who live their like to eat when out. However, you will see a quite a few places advertising local dishes too.
One of the more expensive places offer both a Whale or Puffin sampler. If you have time for two dinners, go for the While at Gamla and the Puffin at Hereford Steikhús which is located at Laugavegur 53B.
