If Siggi Hall had been born a thousand years ago, they'd have written a saga about him. Siggi, Iceland's celebrity chef, has achieved with knives and forks what the heroes of the old Viking tales did with axes and swords. He has travelled, pillaged and conquered. And done a fair bit of ravishing too, though, man of taste that he is, we may be confident that he would have sated his appetites with rather more delicacy than his brawny forebears.

The sagas, Iceland's greatest (and arguably sole) contribution to human civilisation, are half-epic, half-novel. In the literary canon they lie somewhere between Homer and Cervantes. The sagas' heroes (Njal the Wise, Gunnar the Brave, Grettir the Strong) typically leave Iceland in their longboats for Norway or Denmark - or in some cases Scotland, Russia and Constantinople. They terrorise the locals and steal their treasure. Then they settle back home, to great acclaim.

Siggi the Sensual left for Denmark in 1972, when he was 19. The plan was, as he explained it, 'to drink, smoke dope and meet girls' but he also got a job in a restaurant washing dishes. The rest is history. He learnt under a French chef who had worked at London's Savoy, rose through the kitchen ranks, shifted ever upwards from restaurant to restaurant, set up his own place in Norway (where by day he was a ski instructor) and after more than a decade returned home, where he imparted the wisdom he had gleaned to a grateful Iceland via a TV series that lasted nine years and 350 episodes. On 31 December 1999, he quit TV and the next day set up his own restaurant (a Reykjavik legend, named after himself) where he serves 'fried bacalao a la Basque', 'pan-fried foie gras with glazed pear and brioche', 'veloute of shrimps with mussels and champagne chantilly' and ...well, you know the sort of thing.

They know it well, at any rate, in Reykjavik, a pleasure dome of gastronomic delights these days. But around the time that Siggi set off on the first of his Danish adventures they would not have had a clue what you were talking about. 'We were barbarians,' recalls Siggi. 'Our traditional dishes were sheep's head, liver pudding and raw fish and sea bird of one type or another. At home we ate boiled haddock and for a real treat, an anniversary night out or something, it was chicken in a basket.'

Today, food is not only prepared to international standards in Iceland, it is considered something of a national treasure. Otherwise why would the country's president have banged on about it at such length when I went to see him? And how else, for that matter, would it have been Siggi who got the interview for me?

A tall, friendly fellow with vermillion lips, bloodhound jowls, and generous tum, Siggi packs a mean political punch. A day and a half before my flight home, I remarked to him on the phone that it was a pity I hadn't got around to seeing the president. 'Wait a moment,' he said. 'I'll call you right back.' Two minutes later the phone rang. 'The president will see you at 1.30 tomorrow. It's his tenth anniversary but it's no problem. Shall I call back and say you'll make it?'

The next day Siggi drove me in his stately 4x4 to the presidential residence. At the end of a causeway, surrounded by sea and fjords and green hills and distant mountains crowned with gleaming glaciers (it is the scenery one goes to Iceland for, let's be honest, though one does have to eat), sat the modest mansion that President Olafur Ragnar Grimsson has called home these last 10 years. We drove up to the front door, unchallenged, and rang the bell. A young blonde woman appeared. I told her my name. She asked me to come in and please sign the visitors' book. Then a door opened and out stepped a tall, dapper man with a mop of white hair, a controlled smile and gently outstretched hand. He bade me into his study and Siggi followed us in, pausing apologetically at the threshold to make a little speech. Siggi, abandoning his customary informality, addressed his president like a courtier a king - eyes cast reverently down, hands clasped before him, as if in prayer, or supplication. In Icelandic (an ancient language with odd letters, no manifest Latin or Anglo-Saxon roots and places with names like Kirkjubaejarklaustur), he rattled away about what I chose to believe were my admirable human attributes and my impeccable journalistic pedigree. Then he left, closing the door softly behind him. Before revealing the keen interest he had in gastronomy (he was very pleased by the gift of a bottle of finest-harvest Rioja I made him), the president asked whether I had noticed that there had been no 'inspection' when I arrived; that no one had asked me to provide any ID, let alone asked me to take off my belt, shoes and watch and go through a metal detector. Yes, I said, as the thought struck me that I could have assassinated him with my wine bottle right there and then, had I been so inclined. But he was right, yes. If there was one point on which I needed no persuading it was that Iceland (total prison population: 116) was the safest place in the whole world.

'Our local lamb is quite unique, you know,' he said, in exquisitely regal English. 'They are wild animals, really.' 'Wild animals?' I said, conjuring alarming images. 'Yes. They spend most of their lives grazing far, far from humans, in the wild. Icelandic lamb's almost a game meat, actually.'

Food, the president continued, was a metaphor for his country's staggering success of the last 20 years, a period during which Iceland has evolved from almost Eastern European dullness into a country of geyser-gushing cultural and economic effervescence. It is the sixth-richest country per capita in the world and Icelandic companies currently employ 120,000 people in Britain.

President Grimsson said that part of the reason for the Icelandic boom had to do with the habit of his highly educated compatriots (they speak better English than the English, believe me) of travelling to far-flung corners of the earth. These days Icelanders go away to study or work, and hire British serfs. 'We are a people open to outside influences,' the president said. 'We collect the best of what we see abroad and then we return, making Iceland into a sort of Renaissance melting pot of nations. You see the impact all over the economy but perhaps most visibly in the rich global variety of our cuisine. Look at Siggi Hall's famous bacalao, with its explicit Spanish influence. He benefits from the wonderful raw material here, our cold-water fish, and he injects it with a touch of Icelandic ingenuity, too.'

The first place I ate at on the day I arrived in Reykjavik illustrated the president's Renaissance point rather well, though the analogy did not instantly jump to mind at the time. Hornid's Pizzeria was much more than that. Plenty of fettucine and mozzarella on the menu but I went for the seafood soup with shrimps, mussels and scallops and then for the Arctic char, a pink fish, less fleshy than salmon but breathing the scent of the sea. Hornid's, founded in 1979, was the oldest Italian restaurant in town - reflecting the point that until very recently indeed Reykjavik (two-thirds of the population live in this south-western corner of the country) was an overgrown fishing village. Today the reds, blues, yellows and greens of the town's Lego rooftops are at odds with the rampant cosmopolitanism of the place.

There's Thai, there's Indian, there's Chinese, there's Vietnamese, there's Spanish tapas, there are French bistros, there's Argentine meat and fine coffee shops at every turn. And there are top-class restaurants like Vid Tjornina or Laekjarbrekka that blend the Icelandic and the exotic in the manner President Grimsson had advertised. At Vid Tjornina I ate a memorable raw fish starter marinated in lemon with ginger, soy sauce and wasabi. The bacalao that followed - made with olives, tomato and onion - would have raised a cheer in Bilbao. The menu at Laekjarbrekka offered, among other extravagances, reindeer carpaccio with rucola salad, porcini-filled tortellini pasta with lobster tails in garlic sauce and deep-fried camembert with redcurrant jelly, as well as good old-fashioned braised shank of lamb. Plus some very nice, if expensive wines, like a Klein Constantia Sauvignon Blanc I was surprised to find so far from its Cape Town habitat.

And there's also Asian fusion, as in the Seafood Cellar, which has quite possibly the most ample wine list in Reykjavik, and the most polished, if borderline pretentious (hell, we're in Reykjavik, after all, not the Rive Gauche) waiters. The names of some of the dishes on the menu were so hip I wanted to die - vegetable spring roll 'fresh vibes'; snowcrab vs. smoked salmon 'twister'; salmon steak 'dark shadow'; and kangaroo 'shaken not stirred'. The caper and anis, the carrot, nori, yuzu and the smoked eel, bulgar and avocado starters were pretty daring, too. It was a show, a spectacle - heavily produced and pleasingly presented. I had dinner there and enjoyed it.

I had to keep on reminding myself that this was a city where, as Siggi and others kept on reminding me, 20 years ago they only had two restaurants, both of them crap. (This is kinder and gentler than what WH Auden and Louis MacNeice said about the local nosh in their Letters from Iceland written in 1936: 'Soups: Many of these are sweet and very unfortunate: I remember three with particular horror, one of sweet milk and hard macaroni, one tasting of hot marzipan and one of scented hair oil.') I also had to keep on reminding myself, as I sucked down a skyr, a kind of creamy Icelandic yoghurt, with strawberry panna cotta and blueberry sorbet, that this was dinner and not lunch.

The time was midnight as I approached the end of my fused Seafood Cellar dessert, and the sun was still up - low over the horizon, but up. Since before I had sat down at my meal it seemed as if it was about to go down, but it just held on, hovering tantalisingly on the horizon, until at last, around one in the morning, it dipped momentarily out of sight to re-emerge, half a minute later, at what was officially dawn. Magic so strong provokes a childlike wonder in you, and something of the mischievous delight of the little boy allowed to stay up way beyond his bedtime.

Siggi was, I thought, just the tiniest bit sniffy about the heaviness of the Seafood Cellar's reliance on imported grub, yet he took his hat off to its award-winning, Conde Nast-recommended successes. He's a very international chap, Siggi, always travelling to places like Russia and America, as well as to a place in Italy where he gets his wine and olive oil. Much of the time he is away organising an annual Reykjavik bash called Food and Fun that brings together eminent chefs from all over the world each February for a four-day gastrothon in which the visiting chefs cook at local restaurants and then compete to see who can make the best three-course meal out of Icelandic ingredients. Icelanders are a relentlessly modern bunch, who in their 20 years of nouveau affluence have embraced the trends of the northwestern world (no country has more mobile phones or internet access per capita) with almost drunken abandon.

Siggi was Iceland's most famous TV chef during the whole of the Nineties and still today he cannot walk out of his door without being recognised. Which proved to be a blessing the night we went out on the town, as we managed to jump all the queues. He clearly admired the international-class restaurants in Reykjavik but his own favourite (apart, I suppose, from his own, to which we shall turn later) was a traditional seafood place called Thrir Frakkar owned by a mate he called 'Old Wolf' but whose real name was Ulfar Eysteinsson. Despite the name, and a grey face and square shape that reminded me of a sea lion, and a menu consisting of - among other local delicacies - whale and puffin and cormorant, Ulfar was, in all other respects, every inch an Italian. He had the air and sense of fun, the deep-down seriousness in the food but whimsical glitter in the eyes, of the trattoria owner in Sicily who understood that life is short, brutish and - wherever possible - to be enjoyed. He also had a tendency to tell porkies, or at any rate tall tales. Or maybe they were true. The glint in the eye made it impossible to be quite sure. Claiming, for example, to have been a rally driver for 20 years until he opened his restaurant in 1989, he told me that on that very year he bought a dead whale, or at least 27 tons of choice meat from it. 'The whale was killed on 20 July 1989. I froze the meat and it lasted, delicious, for 17 years.' Seventeen years? That would be until ...2006. I said, 'So do you mean the whale you just gave me, the whale I ate raw, sashimi style was ...' Ulfar laughed, or rather gurgled, demonically. 'No,' he spluttered. 'No, no ...we finished the last of it in May.' True or not, the fact of the matter is that I really did enjoy my whale. A minke whale, to be precise, a smaller beast than the ones whose slaughter Iceland has internationally agreed to curtail. It was a deep red meat cut in rough thin chunks that was as tender as any beef steak I'd ever eaten, and - in its raw form at least, and aided by some ginger and wasabi - tastier and more rich.

The raw puffin, cut in thin black strips, was slimy and tough and tasted like burnt rubber marinated in diesel oil. Thanks, but never again. The rest of the food at Ulfar's delightfully simple down-home restaurant - dark, cluttered, not a clever design in sight - was terrific. Above all because it was fresh and Ulfar, who knew how to cook it at just right temperature and for just the right time, had had the wisdom to spare the seasonings and let the sea do its stuff. 'I only have fish from this island,' said Ulfar, who sat at our table at the end of the meal, drinking from a bucket-sized glass of lager. The waiter brought us his equivalent of an amuse-bouche, some deep-fried cod skins. Ulfar looked at me (there was something of Anthony Quinn about him) with expectancy as I crunched the first strip down and laughed out loud in Zorba delight when my eyes told him that it was great. I asked him if he ever felt the temptation to infuse his food with the influence of some other country but he said that apart from the Japanese flavourings he offered as an optional accompaniment to his raw fish and birds, no.

'I love to go to France and Spain and see and smell, but that's it.' Siggi, who might be a star but is modest with it, said that he had to hand it to his friend the Wolf. 'I, by contrast, get most of my inspiration from France and Spain. Ulfar, no. He uses his own imagination and takes his product from our land and our sea. He is one of my heroes, Ulfar. The real thing. My kind of restaurant can be found anywhere in the world. This is an original.'

Not so original as to serve the Icelandic hard stuff, though. No putrefied shark on Ulfar's menu. We didn't even discuss it. Though I did one night, late, at Siggi's restaurant, where I went with my friend Ari at one on a Saturday morning, after visiting two or three of Reykjavik's trendier bars.

But first let me mention the place where Ari, a young veteran of the city's night scene, began our evening. It was an Icelandic fish and chip shop, without the chips, called the Sea Baron where you order and they bring you the nosh outside. You sit, by the harbour, on a rough wooden bench and table. They had puffin and whale and cormorant again. I hadn't tried the cormorant and felt that, in the interests of science, journalistic honour and the readers of this magazine, I probably ought to. I did not. It looked like puffin, only bigger, rounder, fatter and greasier - and just as black. But the lobster soup was not only the cheapest in Reykjavik but, probably, the best.

I told Ari, who was studying film in Paris and had come home for the summer, how impressed I had been by the food in his country. I told him of a restaurant I had found on a trip to the far north of the country, a beautiful island on a fjord called Hrisey. Here, amid so much raging beauty, about as close to the poles as you can get and still find permanent human habitation (160 live on Hrisey), I came across a restaurant called Brekka's where I had a fabulous lobster salad, with fresh greens and olive oil, followed by the richest piece of toughly tender lamb (President Grimsson was right, it was a wild animal) I had eaten in all my life. Brekka's, I remarked to Ari, had kept pace with the Reykjavik revolution. The young chef wore a beret and a wrap-around jacket, in the style of the world's Michelin three-star cooks.

Ari smiled and said, 'Yes, food is part of the revolution we've had in this country since I was born. Food used to be fuel; now it is sensual pleasure.'

We went to a bar called Kaffibarinn that is supposed to be very cool - partly because it is part-owned by a former Icelandic heart-throb actor called Baltasar Kormakur - where we drank Viking beer. We did the same at Bar Q where a band of Icelandic journalists played salsa and sang in Spanish (most Icelanders speak three languages; a lot of them, four or five); then we went to party at someone's flat and then to Siggi's, who joined us for the rest of the night's bar-hopping but first sat us down in his restaurant, gave us a glass of wine and told us how to cook putrefied - also known as 'rotten' - shark.

'The problem with the shark,' Siggi began, 'is that it does not urinate. So this means it collects in its blood and its meat an awful lot of acid and ammonia.' So you don't want to eat it sashimi-style, then? 'You really don't,' said Siggi. 'You might die.' What you do, he said, is cut up the shark into big brick-pieces of meat. (Don't try this at home - in the garden, maybe, but not in the home.) Then you put the shark bricks in a kind of large basin-shaped kiln, made with large stones. You construct this outside, preferably on top of a windswept hill, far away from human habitation. Then you put more large stones, or heavy rocks, on top of the shark meat and leave it for three months. This is the time required for the toxic fluids to drain out of the shark. This is also the time when the meat begins to rot. This is good.

'At the end of the three months,' Siggi continued, 'you take the meat out - now it is softer, but still smells like ammonia probably - and hang it out to dry. After another three months the meat will be firm and cured enough so that when you eat it, it won't necessarily kill you.' You wouldn't recommend it, then, Siggi? I said. 'I would not recommend it.'

Icelandic hot dog, on the other hand, is worth the air fare to the most northerly capital on earth. Maybe it helps that prior to chowing down on my first one I had spent that night out with Siggi and Ari, ending at five in the morning at a frenetically packed high-decibel joint called Sirkus where Bjork (Iceland's second greatest contribution to human civilisation) occasionally comes for a sweaty pump-up.

But no. That's not true. I had several more hot dogs at Baejarins Beztu Pylsur, a little stand by the harbour, before my trip was done and they were unanimously outstanding. And the same. Because I did as the locals did and asked for all the available condiments. Ketchup, mustard, remoulade sauce and a brown, tangy onionish concoction that was just perfect. Though the secret is apparently in the sausages themselves - pleasingly fat and long for a sausage that's a quid a shot and made not of pork but, yes, more of that lamb sauvage.

Siggi's restaurant is at a four-star hotel called the Odinsve, just off the main drag where all the shops and bars are. The setting is quite minimalist, and is simply lit. No dark 'designer' lighting here, nothing special about the walls or what is on them. The only thing that stands out are the white tablecloths and a raised cocktail bar, up a couple of steps next to the kitchen. The barlady is a queen cocktail-maker and the one male waiter is the nearest thing I have seen to a living-breathing Manuel. Borderline ludicrous, he engaged in rather more patter than was appropriate and had a habit, when pouring the wine, of reaching not alongside you but across, and always as you were about to raise the fork to your mouth, raising the danger that instead of chewing on your lamb, you'd do so on his biceps.

The antics of Manuel II seemed lost on Siggi . Food is part of the revolution - it used to be fuel, now it is sensual pleasure He seemed to spend the evening gazing benignly down on his guests (he is tall, remember), his hands held gingerly over his spreading midriff , engaging them in cloudy conversation. He is an epicurean sort, whose relationship with food when he talks about it is tremulously excitable, borderline erotic. Not that he spent all that much time in the kitchen. Siggi, more French than Icelandic at heart, was the restaurant's strategic thinker. The actual work was done by his David Beckham-lookalike head chef. The second night I went, there was a table with a dozen young women on it. After the meal, and amid much squealing, they posed for photographs with ReykjaBecks. Made you wonder whether they'd come for the grub or for the hunk.

But the grub, which also has the Condé Nast good noshing seal of approval, was great. Somewhere between Seafood Cellar pretentious and down- home Ulfar's. Siggi was right when he said that the kind of food he served could be found anywhere in the world. But only in the finest establishments. I began with thin slices of smoked chicken with pesto and cucumbers chopped small, washed down with a rich, green-appley glass of champagne. Then some gravadlax and then some langoustines wrapped in beetroot pasta, in the shape of a spring roll, over a bed of bacalao brandada, a white puree of salted cod mushed with butter and flour and cream, with a bit of alfalfa on the side. The little brick of halibut that followed had a delightful crust of black olives and sat on a bed of white beans, small onions and salmon roe - all of which enhanced, rather than obliterated, the fresh naturalness of the fish.

And so it went on, with plenty of fine wine, mainly Italian, and lots of olive oil (Siggi says he has checked with the big wholesalers in Rotterdam and there is no non-olive producing country in Europe that consumes more olive oil per head than Iceland). Good fresh fare, imaginative but without drawing too much attention to itself.

Dinner at Siggi's cost, as it did at the other high-end restaurants I ate at in Reykjavik, about 60 quid per person. Not cheap but, as President Grimsson was at pains (and I think quite correctly) to impress, a lot cheaper than the equivalent meal in London or New York . The deal you get is all the better when you consider the landscape that's thrown in for free. As a writer I spoke to in Hrisey Island said, 'My grandmother was born in 1900 and died in 1998. In Icelandic terms that means her life spanned from the Stone Age to the Computer Age.' Fascinated by his country's whirlwind evolution, he had another grandmotherly image to convey how drastically his country had changed in the last century. 'She was born in a turf hut and finished her life in a Toyota Land Cruiser.' We could have gone on in this vein all afternoon. Here's one I suggested. 'She was born eating boiled sheep's heads and died eating pan-fried foie gras.' Or, 'She began life drying putrefied shark and ended it nibbling veloute of shrimps ...'

· Reykjavik restaurant contact details: Siggi Hall Restaurant, Hotel Odinsve, Thorsgata 1, 112 Reykjavik (+354 511 66 77), closed on Mondays. Hornid Pizzeria, Hafnarstraeti 15, 101 Reykjavik (+354 551 3340).Vid Tjörnina, Templarasund 3, 101 Reykjavík. (+354 551 8666 ). Laekjarbrekka, Bankastræti 2, 101 Reykjavík (+354 551 4430 ). Seafood Cellar, Adalstreti 2, 101 Reykjavík (+354 511 1212). 3 Frakkar Restaurant, Baldursgata 14, 101 Reykjavík (+354 552 3939). The Brekka Restaurant ( +354 466 1751)

First catch your puffin

Pot roast puffin

I don't care much for puffin and other sea-birds as food, but many people love them and eat them whenever they can. In this recipe, the birds are cooked in milk.

Serves 4

4 puffins
50g smoked bacon
50g butter
300ml milk
300ml water
salt to taste

Puffins should be skinned or carefully plucked and singed. Remove the innards and discard. You can use the breasts alone, or cook the whole birds. Wash well in cold water and rub with salt, inside and out. If you are using whole birds, truss them. Lard the breasts with bacon fat.

Brown the birds on all sides, and stuff them tightly into a cooking pot. Heat the milk and water and pour over the puffins. Bring to the boil and cook on low for 1-2 hours (test the birds for softness). Turn the birds occasionally. Remove from the cooking liquid and keep warm while you prepare the sauce.

The sauce:

30g butter
4 tbs flour
400-500ml cooking liquid
salt and pepper
caramel sauce colouring as needed
redcurrant jelly (optional) to taste
whipped cream to taste

Melt the butter and stir the flour into it as though you are making white sauce. Strain the cooking liquid and gradually add to the butter/flour mixture. Add colouring and spices to taste, and redcurrant jelly or cream, if using.

Serve with boiled and or sauteed potatoes and lightly boiled vegetables, like carrots, peas and brussels sprouts.

· Recipe taken from Helga Sigur&ardttirs Matur Drykkur , Ml og Menning, Reykjavk, (1947). Chefs tip: today the puffin is considered endangered in the UK, so go for Icelandic puffin for this dish