In the desert, very early in the morning, Samir, the Bedouin guide, told me to watch for the green flash. Not an ancient piece of Dunlop footwear, rather the curious atmospheric effect caused by the sun’s rays refracting through ultra-clean air the moment before sunrise. Try communicating that in broken English and pidgin Arabic. I stuck my head out of the tent door. The dunes were sharp-edged with shadow. The only smell was the deep, cool inhalation of dawn. The only sound, after Samir had turned off the stove, was a kind of reverse of sound, a super-silence that seemed to empty the soul of all inner noise. I could see the sun glowing below the distant horizon. Then, for what seemed like at least a second, the green flash flooded the desert like an alien heliograph. A moment later, the skyline erupted with the instant magnificence of the sun, its sudden warmth.

I was in the Sahara, in the Egyptian Great Sand Sea, 200 miles from running water, grocery shops, flushing toilets or e-mail. The 120-mile-long dunes on either side were truly massive, three or four hundred yards high, like endless lines of great white hills.

I climbed one, and spent half an hour going ever onwards and upwards over false summit after false summit. The sand underfoot was surprisingly firm, clean and crunchy, like a pristine beach. The view was extraordinary, row after row of dunes stretching away to the east and the west. In every direction lay sand — white, grey, pink, light orange, dark orange, even purple and shades of blue. Down below, I could see the camp and five tiny black figures. In our two-week trip, we did not meet, or even see, a single other traveller.

The stated purpose of the expedition was to find a new route through the sand sea down to the Gilf Kebir, a 300-yard-high plateau in the south of Egypt that’s as big as Switzerland, but without a single cuckoo clock, chocolate factory, lake or even ditch. The Gilf is the most profoundly arid region on earth in terms of ground water, or lack of it.

The sand sea itself was first crossed in 1933 by a group that included Dorothy Clayton East Clayton, the real-life model on whom the Kristin Scott Thomas character was based in The English Patient. The Gilf Kebir is the site of the “Cave of the Swimmers”, which, if you’ve seen the film, is where Kristin Scott Thomas says a romantic goodbye to Ralph Fiennes and dies before he can return to save her. The cave is decorated with mysterious 5,000-year-old paintings of diving men, the so-called “swimmers”. The cave was our goal. A good destination for the driest place on earth.

We were travelling in 4WD Toyota Hi-Lux pickups with a crew cab for passengers. They were surprisingly luxurious, a lot more comfortable than pickups look parked on your local building site. The company was a new one, Tribe Expeditions, and the expedition (three of us) was equalled in number by the two Bedouin drivers and the tour leader, Mahmoud. In the Great Sand Sea, only cars will work — there is simply too little water for camels, which can only traverse its corners.

WE LEFT Cairo by road to the oasis of Bahariya. En route, we managed to lose Samir, who took a wrong turning at the pyramids and only noticed he was heading towards Sudan after 20 miles.

“I thought Bedouin had an in-built sense of direction,” I chided Mahmoud.

“It only works in the desert — you’ll see.” He was right, of course. At any point in the day, we’d test Samir on the time, which he could tell by the sun, and the direction of east. He was always right about both — to within seven or eight minutes of the correct time.

After Bahariya, we headed across the desert to Siwa, the oasis where Alexander the Great sought the advice of the oracle. Here we turned south into the Great Sand Sea. We had spades, perforated aluminium sand plates, tow ropes, nearly a ton of fuel and a ton of water. We were rationed to four litres of water a day for everything. The 1933 expedition allowed themselves only five pints a day, but then we were travelling in May, about the hottest month you can safely travel in. We had tents, but after a few days I copied the Bedouin by sleeping in my bag directly on soft sand.

At night, every star was visible as if far closer than usual. Perhaps it isn’t strange that such bright stars banish all feelings of loneliness.

A day from Siwa, already deep in the sand sea, we hit our first sandstorm. This is brilliant, I thought, as I stood on the roof of the parked car, looking out over the roiling solid cloud below me. It was like breaking through the clouds in an aeroplane. Only dust storms can rise hundreds of yards in the air — sand is too heavy to go more than a few yards up. But, for me, back on the ground, head wrapped in a Yasser Arafat-style headscarf like Samir showed me, the storm quickly lost its novelty.

Without years of Bedouin experience, my scarf soon developed leaks (you wrap it like a bag over your entire head). I rolled in my sleeping bag up against the car. But wheels, even those shod with outsize sand tyres, provide scant protection from a howling gale. All night I heard the suspension making ominous creaking sounds as the sand undercut one side and piled up on my side. By morning, the car was at a precarious 30-degree lean and I was completely buried, with only bits of the bag showing above the drift. Sand got into my hair, neck, nose, ears and eyebrows, and for days afterwards, I was trying to comb it out with my toothbrush, but my toothbrush had sand in it too. Alain, an irrepressible French fellow traveller, whose tent blew down in the night, met me in the morning with the telltale red, sand-filled eyes. “That,” he said with venom, “was bloody ’orrible.”

But the day following the sandstorm was marvellous. We continued heading south towards the Gilf, driving for hours along the corridors between dunes and flying up and over the whaleback dunes that block them. Sand driving is all about speed, but when there is nothing to focus on, you feel as if you are flying into an orange fog. All sense of perspective is distorted. A spot in the distance could be a tiny rock much closer than you think, or a giant boulder miles away. Most accidents occur in dunes, where a drop suddenly appears out of the seamless sand. And then you get stuck.

Sand plates shoved under each tyre give you enough grip to get moving, but it’s the quality of the pushing from behind that really counts. With noon temperatures in the high 30s, it was exhausting work. Alain stripped off and got sunburnt. I wore a short-sleeved shirt, but Samir always kept his rollneck sweater and woollen long johns on under his kaftan-like galabiyya.

WHENEVER we stopped, Samir would find things: an ostrich egg — it looked new, but ostriches have been unknown this far north for more than 200 years; prehistoric stone tools, fashioned with delicate precision into sliver-like knives and chisels; a fossilised shark’s tooth, the tooth black in its white-bone setting; second world war petrol tins, still with paper Shell wrappers; a forest of petrified palm trees; fragments of silica glass, a natural glass found only here in such a pure state — Tutankhamun’s pectoral scarab was made of such glass. My eyes were soon glued to the ground like a demented beachcomber — and towards the end of the trip, I was rewarded — an intact handmade water jar sticking out of the top of a dune. Dropped, perhaps, by a wayward camel caravan many hundreds of years before.

As we approached the Gilf Kebir plateau, its 300-yard-high walls hardly seemed to get closer. Because visibility is so good, they looked six miles away when they were more than 30. Then we hit the tongue of sand that blocks the northern entrance. Finding a new route across this huge barrier was the hardest part of the trip.

Mahmoud hurled his pickup at dune after dune, often having to reverse back down when he failed to make it to the top. At one point, we got stuck up to the axles in a box canyon of sand. No way out. In the end, we solved it with a running road of sand plates, pulled out from behind and dashed to the front in a frenzy of scuffed knuckles, skidding and deeply disturbing engine noises.

We arrived at the Cave of the Swimmers an hour before sunset. Yellow light bathed the entrance at the foot of a cliff. By now, I was used to the way the silence made you calmer in tremendous downward plunges, similar to the way a plane drops bodily during turbulence.

Inside, I saw rock paintings of buffalo, spear-carrying hunters, handprints in red ochre, and the swimmers. They were small, hand-sized, potbellied men, painted in black on the crumbling limestone, their thin arms and legs extended as if in a swallow dive. Perhaps their diving was the same plunging towards an inner calm I felt. Outside, Alain said: “Coming ’ere, all this way, to see this... it’s like a new religion.”

Nobody disagreed.

Travel details: Tribe Expeditions (00 20 2259 1311, www.tribe-expeditions.com ) has 12-day tours of the Great Sand Sea and the Gilf Kebir from £940pp, excluding flights. British Airways (0870 850 9850, www. ba.com) flies from Heathrow to Cairo; from £408.

Times recommends

• Smugshots special: a new perspective
• The 15 best Mediterranean hotels under £100
• Britain's best rivers for swimming