Grandparents were aghast when we said we were taking our children (aged six, nine and 11) on holiday to Yemen. They recalled the deaths of the four tourists in December 1998 and pointed to the stark Foreign Office advice that this remote corner of Arabia is as dangerous as Somalia, Afghanistan or Chechnya.

Remembering the four years we had spent in Yemen in the early 1980s, we were sure no harm awaited us. Nevertheless, in search of reassurance, I emailed an acquaintance in Sana'a but failed to get a reply. Eventually, the reason became apparent - she had been kidnapped.

Fortunately, as with other "traditional" Yemeni kidnappings, all was speedily resolved. "Hostages" generally enjoy the hospitality offered them, call home on satellite phones and usually receive a parting gift. The tribesmen from the fringes of the Empty Quarter who carry out these publicity stunts get the clinic, school or whatever else they feel the central government has been remiss in supplying.

The children's surprise at the large number of armed soldiers at Sana'a airport gave way to astonishment as we drove into the medieval old city. A lone passer-by, delayed on his way to bed after the all-night bustle of Ramadan, insisted on accompanying us to the door.

We rang the bell and, far above us, our host pulled the cord that shot the bolt of his ancient wooden door.

Downing rucksacks, the children raced up the narrow staircase of the eight-storey house, relishing the breathlessness induced by the rarefied air. Three pleasantly disorienting days followed as jet-lag, the 7,500ft altitude, the rhythm of Ramadan and the thrill of the unknown convinced the children that a week was passing.

Losing ourselves in the labyrinth of the suq, we were stunned to find everything so affordable, £1 buying 260 rials compared with only 10 in the 1980s. The boys were soon cheaply kitted out in colourful sarongs and curved daggers, our daughter in a skirt, leggings and headcloth.

Passers-by were delighted to see tourists once more. Abandoning the warnings of "stranger danger" preached by British schools, the children soon got used to being patted. My partner marvelled at her ability to move at ease through the streets of a capital city at 2am. Our welfare seemed to concern the whole world. We could not stop to buy without strangers intervening to make doubly sure we were not being overcharged.

The rigours of fasting seemed not to dent the geniality of the swarming crowds. After the sunset meal, their exuberance was infectious, their curiosity even more pressing. Invitations to come and chew qat , the favoured recreational drug of most highland Yemenis, were rebuffed with difficulty. Our younger son was grabbed by a man keen to teach him to dance. Within seconds, the road was blocked by a circle of swirling dancers, daggers flashing.

In the suq, we were accosted by a stern man, whose bearing, expensive dagger and clean clothes showed him to be a tribesman of some rank. "Would we like to be kidnapped?" he asked. He could get his tribe to do the deed and would split the profits with us. It began the first of many discussions about the solitary fatal terrorist incident which has destroyed the tourist industry.

Some 84,000 tourists visited Yemen in 1997; fewer than a tenth of that number came in 1999. A developed tourist infrastructure (a hundred local tourist agencies, comfortable hotels in major towns, a much-improved road and air network) stands idle. We did not meet a single tourist for the first two of our three weeks in Yemen.

Dogs dozed in the shuttered doorway of the main tourist-information office in Sana'a. Disturbed from his own Ramadan slumbers, the man in charge rallied a smile and a prayer for better times as he opened up.

We flew from Sana'a to Hadramawt, not risking the overland route through the ancient city of Marib and across the dunes of the Empty Quarter. Here the writ of the tribes carries more weight than that of the government, and travellers to these remote parts are advised to pay £200 for a group of Bedouins to drive ahead and alert would-be brigands that the travellers are locally vouched for.

We descended from the plateau into the claustrophobic world of the 200km canyon of Wadi Hadramawt. In Sayyun's best hotel, air-conditioned doubles with satellite TV cost only £10-£15 a night. In Tarim, we stayed in an ornate former palace, built entirely of mud (except for the swimming pool). In Shibam, "the Manhattan of Arabia", one of three Unesco World Heritage Sites in Yemen, we wandered among the tower-houses, dodging goats and chatting to souvenir-shop owners desperate for a return to better times.

Leaving the sealed roads, we entered the side wadi of Daw'an, fabled for its honey, the acumen of its businessmen and the grandiose mansions with which they proclaim their success.

Then in one memorable day, we drove, perched on the roof-rack of our Landcruiser, from the Hadramawt to the Indian Ocean, crossing 300km of cold, stony steppe. The day ended in a fine hotel overlooking the sweeping bay of Mukalla and conversations with men eager to practise English and reminisce about the "paradise" of pre-Marxist British rule.

The long drive from Mukalla to Aden had its distractions: a school of dolphins leisurely cruising along the shore; climbing to the rim of an extinct volcano; chasing massive crabs along a deserted beach. Most exciting was the VIP treatment from the Yemeni army. In this area, where tourists were killed in 1998, the government takes no chances. For hundreds of kilometres, we were escorted by a succession of groups of armed men. The total premium paid to many soldiers for this additional travel insurance, negotiated in instalments at each check-point, was £15.

In the time-warp of Aden, we stayed in Crater, our hotel next to the Hurricane Cinema, from which we ventured to eat ridiculously cheap fish. Struggling to get back on its feet in the aftermath of the 1994 "war of secession", Aden is surely set to rival Goa and Mombasa as a winter-holiday destination. Its imposing physical presence, its perfect coves and beaches, the excitement of the balmy nights made it hard to leave.

Christmas Day saw us chatting with the operator of a camel-driven sesame oil mill before putting the Landcruiser to its sternest test as we scaled the terraced slopes of Jabal Hufash. Sitting under a bush for a festive lunch, my daughter spotted a partridge perched in a prickly pear tree.

The children were made much of in the mountain-top community of Manakha, poised on top of the pass linking Sana'a to the sea. The Hajjara Tourist Hotel provided riveting entertainment, waiters and cooks nightly metamorphosing into mesmeric dancers, singers and drummers. We tottered on donkeys over the mountains to a pilgrimage centre for a schismatic group of Ismailis.

A final surprise lay in store. I looked round and my daughter had disappeared. Minutes passed before she re-emerged from a house wearing a veiled headdress. She could not be parted from it.

I was photographing her when a bearded man berated me for my lack of respect for Islam. Did I not know that Yemeni women should not be photographed? On realising she was my daughter, he slunk away, stricken with embarrassment, to the amusement of bystanders.

As the millennium dawned, the children braced themselves against the 3,000m chill of Yemen's highest town. New Year, as with Christmas, went blissfully unremarked by a people confident in the strength of their ancient culture and determined to overcome obstacles and build a self-reliant, and increasingly democratic, state.