It is crunch time at La Almuña, a converted farmhouse in deepest Andalusia, and Hugh Arbuthnott, one-time City gent and Black Watch officer, is reviewing his troops.

“Some of you may be sitting in fear and trembling at what lies ahead: afraid of how difficult the walk might be, afraid of letting yourself down, afraid it might be too much for you. Well, don’t worry. It’s not a route march. Go at your own pace. Stop to enjoy the birds and flowers. Take pictures of the views. We’ll be there to care for you every step of the way, with mules to ride if the going is too tough.”

The troops – 15 visitors who have signed up for a week’s progressive walk in one of the most beautiful corners of Spain – are all on the wrong side of 60, and include a judge, a solicitor, a retired borough treasurer, two former nurses and me.

La Almuña is where the Arbuthnotts launched their Andalusian walking safaris nearly two decades ago. Today, always the consummate host, Hugh still accompanies the walks, while Jane, his wife, provides the logistics, rustling up marvellous suppers and ferrying picnics to preplanned lunch spots along the route.

Spain's secret beach

In July and August the levante wind on the Costa de la Luz drops away, leaving smart cookie Anthony Sattin in his own private paradise

Related Internet Links

• More articles on Spain

Related Links

• Spain's secret beach

The farmhouse is an idyllic spot, perched high in the foothills of the Serrania de Ronda. Looking south to the coast, a two-hour drive away, I can see the blue sugar loaf of Gibraltar – Jebel Tariq, as the Moors called it – and, fainter still, the summit of Jebel Musa, across the straits in Morocco.

The closeness of Africa reminds us that, throughout the week, we will be walking in the frontier country of Moorish Spain. The pueblos blancos – the little white towns of Andalusia, such as Jimena de la Frontera and Cortes de la Frontera – were all frontier citadels at the time of the reconquest. Here, far from the crowded costas and their racetrack highways, in the great patrimonial forests and gaunt sierras, the Moorish Al-Andalus lives on, a land of silence and wheeling vultures, where lonely watchtowers still guard the passes and the scent of gorse hangs in the wind.

Our first day’s walk takes us into the Parque Natural de los Alcornocales – named after the cork oaks that are such a distinctive feature of the Andalusian countryside. Here, together with Canary oaks and other species, they form one of Europe’s largest Mediterranean forests.

First, though, we are introduced to Pedro, Hugh’s veteran muleteer, and his three pack mules. Decked out in scarlet pompoms, they make a brave sight, as if setting out for a country fair. Slung over their backs are straw panniers in which, Hugh tells us, are our elevenses: rich slices of Dundee fruitcake, to be accompanied by a choice of the best chilled fino or Jane’s incomparable homemade lemonade. Better still, they will carry our day bags and even our water bottles, allowing us to walk utterly unencumbered.

WE BEGIN with a steady climb through the matorral, the pungent tangle of Mediterranean scrub that covers the mountainsides with lavender, rosemary, cistus and broom. Stars of Bethlehem shine in the grass like fallen snow. Gladioli add splashes of purest magenta. There are orchids, too, and unfamiliar butterflies: Spanish festoons, Moroccan orange tips, sulphur-yellow Cleopatras; and, as we reach the base of the mountain the Moors called El Hacho (the Axe), we put up a peregrine whose harsh scream echoes among the crags.

The flowers are unbelievable, but the sun is relentless, the air melting and quivering all around us as we gratefully seek the shade to rest and regroup before pushing on through an Arcadian countryside in which blood-red poppies bloom and bee-eaters dive among the oaks.

Back at La Almuña at the end of the day, as the light turns to gold, packs of swifts scythe overhead, describing endless arabesques against the sky. Higher still, flocks of honey buzzards, fresh from Africa, are drifting north on their spring migration, while the nightingales in the valleys below seem to sing louder than ever.

Next morning, our luggage already on its way to our overnight stop, we set off into the adjoining Parque Natural de Grazalema. The park is huge, and a stronghold for griffon vultures, with at least 600 breeding pairs. Soon, the cork oaks close around us and, apart from the constant calls of cuckoos, we walk in silence among trees so old, they must have been growing here since the time of the Armada.

We stay the night at Cortes de la Frontera, 2,000ft above sea level in the Sierra de Libar. In this high country, the air is crisp, but the sun burns just as fiercely. Above us, the bald limestone summits loom like a bad dream.

Hugh knows this will be the toughest walk of the week, so has decided to kick-start the day with a traditional Andalusian breakfast, not in our hotel, but at a private clubhouse in the centre of Cortes: toast rubbed with a clove of garlic, then drenched in olive oil and covered with a choice of sliced tomato or air-dried ham; and, to drink, strong coffee and, for those with an iron constitution, a shot of sol y sombra (brandy and anise).

Yesterday, we bade farewell to Pedro and his mules, and today we are joined by new companions – the tireless Alonso and his two lopeared donkeys, Patch and Pilot. The red tassels on their harnesses swing gaily as we set off, but the path stretches before us like a penance, a cobbled stairway zigzagging into the sky over stony hillsides, with only an occasional stunted oak for shade.

The Moors built this track, Hugh says, probably using Christian slaves, and patrolled it on their sure-footed Barbary ponies, keeping watch over the no man’s land between themselves and the armies of Catholic Spain.

Even in these barren karst lands, flowers bloom: yellow anemones, peacock-blue pimpernels and ghostly spires of asphodel. At last, we reach the high pass and begin to descend into a hidden valley suspended high in the sky between twin mountain ranges that shut out the rest of the world. This is the Llano de Libar, which I saw 16 years ago, when I was last here; but then the sun-dried pastures were devoid of life. “You should come back in spring,” Hugh had said. “The grass is so full of wild flowers, you can barely move.”

That vision had haunted me ever since, and here I am again in this magical valley, timeless and inexpressibly remote, my favourite spot in the whole of Spain – only now it is entirely carpeted by flowers, just as he’d promised.

Scattered across these lonely pastures stand drunken oaks leaning this way and that; hobbit trees with arthritic branches and hollow trunks, each in its own deep pool of shade, watching the silent centuries pass.

Further on, we pass a shallow pool where clear water bubbles up from the limestone and hundreds of frogs roar from the reeds. And, at last, after walking for nearly five hours, we are greeted by Jane with a picnic under the trees: chilled gazpacho and cold roast quails, served with tender spring vegetables from her garden, followed by local sheep’s cheese with quince jelly, walnuts and raisins soaked in brandy.

We spend our next two nights at El Vinculo, a beautifully restored 18th-century olive mill near the picture-postcard village of Zahara de la Sierra, having been given a rest day to get over our climb. Hugh offers to drive us to Grazalema, one of the prettiest of the pueblos blancos, with cobbled streets and flowering balconies. Apparently, this is where the rain in Spain mainly falls – as much as 80in a year – but not today.

In hot sunshine, we lunch in the village square, then drive on to the Puerto de las Palomas, high in the mountains, where orchids – the park has nearly 40 species – bloom by the roadside and ibex stare from the dizzy crags. Up there, Hugh says, live a pair of golden eagles that have learnt how to kill young ibex by knocking them into the void below.

On our last day, Hugh has obtained permission for us to walk to Ronda through the woods and flower meadows of the Marques de Salvatierra’s private estate. At the end of it, tired and dusty after the nine-mile slog in burning sunshine, the trekking troops enter the town like conquering heroes.

Brian Jackman travelled as a guest of The Walking Safari Company

Travel details: trips with The Walking Safari Company (www.walkeurope.com) can be booked through The Ultimate Travel Company (020 7386 4646, www.theultimatetravelcompany.co.uk). An eight-day walk from La Almuña to Ronda starts at £1,365pp, including accommodation (with two nights at La Almuña), all meals (with wine at lunch and dinner), luggage transfers, support staff, muleteers, an English-speaking guide and transfers to and from Malaga airport. Or book through Andrew Brock Travel (01572 821330, www.coromandelabt.com).

Getting there: La Almuña is a two-hour drive from Malaga, to which there are direct flights from more than 20 UK airports, as well as Dublin, Cork and Shannon. Airlines include British Airways (0870 850 9850, www.ba.com), Iberia (0870 609 0500, www.iberia.com), Flybe (0845 675 0681, www.flybe.com), EasyJet (www.easyjet.com) and Ryanair (0871 246 0000, www.ryanair.com ).

Times recommends

• Dubai cheaper than Doncaster as room rates tumble
• World Cup 2010 - how to follow England
• Copenhagen: Europe's greenest city