Ali took a hunk of camel meat and carefully chopped it into tiny cubes before throwing it into a pan. Then a couple of tomatoes, an onion, some salt. After a sip from his tiny glass of tea, he poured in some water, then measured out a few handfuls of macaroni. As the stew bubbled away on the fire, we lay back on the dunes and chatted, while his nephew played a traditional Tuareg game using matches stuck in the sand.
Half an hour later, the concoction was ready, along with a fiery lamb-and-lentil soup and tinned fruit salad. Driving across the desert makes you hungry, even if you are just sitting in the back seat listening to rai music, gazing out at the odd tree, and playing a rather limited game of I spy ("I spy with my little eye something beginning with 'S'." "Sand." "No." "Sun." "No." "Sky." "Yes!") Even camel and macaroni tasted good after such a busy day.
There were a couple of campfire songs and then, stuffed with food, I climbed to the top of the biggest dune. Before me lay the desert of our dreams, the stuff of fantasy: all around, for hundreds of miles, a sea of golden sand whipped up into giant waves. It was almost a full moon, and an oasis glistened below, with palm trees and reed beds reflected in waters fed by underground rivers. That night, as we lay sleeping under the Saharan stars, a jerboa feasted on a dropped apple core beside my feet and a fennec fox padded past our heads, their nocturnal jaunts given away by their footprints.
We were in the Ubari sand sea, midway through a week in Libya or the Great Socialist People's Libyan Arab Jamahiriya, to use the official title. "Why are you going there?" friends had asked, followed quickly by, "Isn't it dangerous?"
The reality is a warm welcome in a country coming in from the cold. For more than three decades, Libya languished under its quixotic ruler, who turned his nation into an international pariah. Now Gaddafi says, "The old times are finished". He has accepted Libya's responsibility for the Lockerbie bombing, abandoned plans to build weapons of mass destruction, and, with sanctions lifted, hopes to attract planeloads of foreign investors and tourists. And Libyans seem rather pleased to see you, a sign that better times may be on their way. "You come to Libya, we like you," I was told several times. "Tell your friends they are welcome."
It remains a rather eccentric dictatorship, from its unique ideology to the green flags fluttering everywhere. The opening-up has not been without setbacks; shortly after I returned, a British cruise-ship and hundreds of Western airline passengers were turned away because they did not have Arabic translations of their personal data. Successful new arrivals are greeted at Tripoli airport by a faded picture of Gaddafi in his trademark sunglasses the first of hundreds of such images you come across on walls, shops and hotel lobbies and if travelling in a party of four or more, you will end up with a policeman in tow. Luckily we were three, so were met only by Mustafa, our likeable guide who once lived in Bournemouth, had an encyclopaedic knowledge of history, and enjoyed bad jokes.
We spent the afternoon in Tripoli. It was Friday, so the souk was empty, the city sedate. The scent of shisha pipes hung heavy on the street corners, while families treated themselves to trays of pistachio-filled cakes oozing with honey. We bought some baklava, and ate them sitting on the edge of the fountains in Green Square, created to rival Moscow's Red Square, at the heart of the city. A tiny gazelle stood nearby, tethered to a red seat garlanded with plastic flowers, the props for a street photographer.
On one corner of the piazza, next to a slightly tragic lake built in the shape of Libya, is the national museum, home to a celebrated collection of classical mosaics, statues and artefacts. There are also, rather incongruously, some stuffed two-headed animals and a light blue VW Beetle, used by the Great Leader as he stirred up dissent against King Idris in 1969. Everyone took pictures in front of it. The upper floors are dedicated to the revolution, and as I wandered past a bronze of Gaddafi on a horse, a man whispered sarcastically, "Another Caesar, just for us, eh?". He seemed oblivious to three "secret" policemen sitting nearby in a roped-off area, resembling an exhibit in Tate Modern.
In the last room, hanging from the ceiling, was a decrepit chunk of wood. "What's that?" I asked, jokingly, to be told that it was the gallows for Omar Mukhtar, theresistance hero executed in a concentration camp by the Italians, and immortalised as The Lion of the Desert by Hollywood. As Mukhtar died, his glasses fell off and were retrieved surreptitiously by a small boy. They too are preserved in the museum.
Later, we wandered along the city's wide streets, shaded by jacaranda trees and framed by elegant, white Italianate buildings, the crumbling legacy of Mussolini's short-lived African empire-building. Dinner was lamb tagine and grilled fish, eaten in the shadow of a Roman arch decorated with griffins and sphinxes, and dedicated to Marcus Aurelius. In Britain, there would be hefty charges and lengthy queues to see such a treasure; in Libya, it is part of the street furniture, with cats wandering around and kids playing football beside it. In the souk, we saw Roman columns turned into cornerstones for homes and shops.
The relaxed attitude to antiquity made more sense the next day. After a 90-minute drive through unexpected rain, we came to Leptis Magna. I don't normally get excited by old stones, but this was something else: one of the great Roman cities emerging out of the sand, and barely a visitor in sight. A Punic trading port, it was developed under Septimus Severus, the only African to rule Rome, as the empire's most fabulous city. At its peak, it was home to some 80,000 people, who grew rich shipping animals, ivory and olive oil.
Buried by the Mediterranean sands, Leptis Magna re-emerged at the start of the last century, although much still remains beneath the ground. It is not just huge; it is also astonishingly well preserved.
Parking the car in a eucalyptus grove, we strolled down towards another imposing triumphal arch, this one built in AD203 for Septimus's visit to his home town. Forests of marble columns reached for the sky all around us, and intricately carved limestone poked out from the ground, the rubble of the Roman Empire. As Mustafa brought the city back to life for us, we wandered into bath houses with complex heating systems and frogs swimming in the water. We walked over intricate mosaics, then through fora and temples, theatres and warehouses.
Mustafa pointed out a phallus carved in the ground, gargoyles leering from the walls of the basilica, holes used to measure olive oil and rice in the marketplace. In the lavatorium, many of the seats still intact, he delighted in explaining how seven slaves would play music to hide the noise of 48 men excreting at once. And finally, the amphitheatre, dug out of a quarry beside the sea, where 16,000 people would come to watch gladiators fight for their lives.
That evening, we flew to Sabha, Libya's second city and gateway to the Sahara. An unremarkable place, it is where Gaddafi went to school, and it remains a stronghold of his regime. We were greeted by cryptic slogans in Arabic and English on the walls of the terminal: "The party system aborts democracy"; "Democracy is popular rule, not popular expression"; "Representation is a falsification of democracy" all taken from Gaddafi's Green Book, which outlines his rejection of liberal democracy, children's nurseries and wrestling (available for five dinars at all bookshops in Libya, good or not; it makes an excellent present).
We spent the night at a campsite in a small zoo. Breakfast was croissants and coffee, watched by several ostriches poking their heads on to the dining terrace. Then we set off in a Landcruiser for the Sahara along Wadi al-Hayat (The Valley of Life), which used to be called Wadi al-Ajal (The Valley of Death) until Gaddafi decided that it was too depressing a name. The desert here was closer to scrubland, apart from patches of green where farmers grew broad beans, barley and grapes. Gradually, the sand took over, broken only by the tufts of acanthus plants. We stopped for lunch, hiding from the sun under an acacia tree, then played boules with handfuls of the wild gourds lying around.
As we left, winds began to whip up the sand. Before we knew it, we were in the midst of a sandstorm. We ploughed on while Ali, our driver, looked anxiously at tornadoes in the distance. The storm cleared as quickly as it had arrived. With distorted music blaring from the stereo, we chewed dates, crunched cashew nuts and stared into the distance. A family of camels plodded by. We stopped and dug into the sand; it went from yellow to purple to white in one handful. As night fell, we reached our destination, the lunar landscape of the Messak Settafet plateau. I fell asleep listening to my iPod and watching shooting stars in the Saharan skies.
Rising early, we set off along Wadi Mathkandoush, once a raging river before the desert engulfed the area three millennia ago. Along the valley walls were rock carvings made 12,000 years ago by the prehistoric people. There were lions, elephants, giraffes, hippos, ostriches and antelope. On one rock, a strange crocodile on long legs; on another, a pair of weird dogs or devils reared up on their hind legs. A bull was strikingly similar to some drawn by Picasso; its lines caught the creature brilliantly.
This astonishing open-air gallery continues for seven miles. Sadly, many images are splintering, the rocks tumbling into the wadi, and there are fears that nearby oil-drilling is speeding up their destruction. As the sun rose, snakes came out to sunbathe. We walked back to chat to the Tuaregs who had appeared at the site's entrance to hawk jewellery, thumb-pianos and other trinkets. One of the salesmen asked me to peer into his mouth; a molar was clearly rotting, but I had no drugs to give him. As Ali went through his tea-making performance, then poured us tiny, frothy glasses of sweet, black Algerian tea, it was not hard to guess the cause of his pain.
Another day, another ancient civilisation. This time it was relics of the 3,000-year-old Garamantian Empire in the town of Jarmah, but by now we were getting a bit blas; it seemed rather run of the mill after what we had seen already. Again we were the only visitors, free to clamber around the remnants of this ancient mud-built city.
Far more interesting in the richest nation in Africa, a land where petrol is cheaper than water, were the long queues at the petrol station. They had run dry, a testament to Gadaffi's economic mismanagement. I chatted to a man who told a story of how a Dubai prince had admired the wealth of Libya during a visit in 1970, saying that one day he hoped his nation would be as successful. The man smiled ruefully at the irony: "We have a saying in Libya: if you think too much, you end up dizzy."
As we waited to fill the car, we drank cappuccinos a welcome legacy of Italian rule. I met a couple of friendly Nigerians, who told me that they had spent 10 months travelling from Lagos, en route to Europe. I gave them some money to buy lunch as we headed off back into the desert. A couple of days later, we saw the blue fishing boats used to transport desperate Africans across the Mediterranean.
The car finally refuelled, we ploughed up the first of those magical Saharan dunes and sailed off into the Ubari sand seas. The next 24 hours were the highlight of the trip: bouncing over dunes, floating in sulphurous lakes that appeared miraculously in the desert, watching mirages disappear, playing guitar with a Tuareg musician, and sleeping under the stars.
Back in Tripoli, we spent a morning wandering round the souk, now packed with shoppers. Unlike elsewhere in North Africa, there was no hassling, hustling and bartering just the odd shout of welcome. Elderly Berber women with tattooed faces sat with small trays of food or jewels for sale. Migrants from Mali and Niger bent over sewing machines. One stallholder gave us some mint to eat as we passed by, another some dates. Pausing to admire colourful Tunisian ceramics at the 19th-century Gurgi mosque, a worshipper waved and beckoned me in to take photos.
As we stopped to examine a furious-looking eagle tethered beside cages packed with dogs, tortoises, pigeons and gazelle, the pet-shop owner proudly showed me his collection of snakes. Destined to be used in traditional remedies, they were kept in plastic bottles draped on a door handle. "If you like, I can get one out for a picture," he said, reaching into a bottle. We left quickly.
We went on to the fish market, where we chose fat prawns and squid and mullet that was then barbecued and served up with six exquisite salads in a temple to plastic floristry. Cline Dion warbled in the background while we watched an old man in a skullcap fishing off a jetty. Afterwards, we went off to see more Roman ruins at Sabrathah, 45 miles along the coast. The location was stunning, as was the theatre rebuilt by Italian architects in honour of Mussolini but the site is less spectacular than Leptis Magna, partly because so much of the city was built of sandstone, which has dissolved over the centuries.
That night, with a bank holiday looming the next day, Tripoli burst into life. Extended families poured out of noisy restaurants while young men in Juventus shirts and designer sunglasses hung out in the cafs. Every few minutes, a wedding party would pass, horns honking as brides buried in frothy white dresses were carted back from the beauticians. After a final couscous, we sat drinking coffee and sweet cakes.
It was a typical Mediterranean scene apart from all the fluttering green flags and the giant picture of the Great Leader staring down at us from the wall opposite.
Specialist tour operator Simoon Travel (020-7622 6263; www.simoontravel.com) offers tailor-made and group tours to Libya. A 10-day Land of the Tuareg tour starts at 1,495 per person. The price includes return British Airways flights from Heathrow to Tripoli, internal flights, transfers, full-board accommodation, all activities, admission fees to sites and visas. The passport stamp and translation (see below) is not included but can be arranged for 65.
National Jamahiriya Museum, Red Castle, Tripoli (00 218 21 333 0292). Open Tuesday-Sunday 8am-1pm, Friday 2-4pm only, closed Monday. Admission free.
Red tape & More information
British passport-holders require a visa to enter Libya. Those bearing an Israeli stamp will not be permitted for entry. All visitors must now also have an Arabic transcript of the details page printed in their passport, prior to visa application. The Identity and Passport Service (0870 521 0410; www.ips.gov.uk) can provide a stamp and template for a translator to work from. Visas must be applied for through a travel agency and cost 100 for a single-entry tourist visa.
The People's Bureau of the Great Socialist People's Libyan Arab Jamahiriya, 15 Knightsbridge, London SW1 (020-7589 6120; www.libyan-embassy.co.uk).
Libyan Tourism: www.libyan-tourism.org