A guide in a van picked me up off the morning ferry and hauled me up a mountain road for 30 bouncing minutes. At the top, we got out, walked a dusty track, stumbled into a dip, squeezed through a rocky cleft... and confronted a sight so unexpected that it left me frozen to the path.

If you want to understand Cape Verde, this is the way to do it - standing high above Porto Novo on the craggy island of Santo Antão. Behind me, bare volcanic slopes swept down to a rusty desert plain, the stark landscape fantastically empty, yet giving way eventually to the still bigger emptiness of the blue Atlantic.

But the island's microclimate meant that I was staring into an immense valley so green, fertile and stupefyingly beautiful that it seemed to belong to another place entirely. A zigzag path careered 1,200m (4,000ft) down into the heart of this other world. My guide pointed and together we set off downhill for the hike of a lifetime...

Cape Verde can sparkle, even though its history is largely one of misery, drought and bad luck. Lying 300 miles (500km) off Senegal, this tiny nation - independent for only 33 years - is made up of ten volcanic blobs, all of them uninhabited back in the 15th century when the Portuguese arrived.

Since then, the islands have been known for slave-trading, meagre sugar cultivation, a little transatlantic refuelling work and not much else. But this is changing, thanks to a rush of tourism that benefits from excellent beaches, mild year-round temperatures and little rain. Now the coastal areas, especially on Sal and Boa Vista, are filling with pasty European bodies and signs proclaiming bold new resort plans. Paradise is undergoing a paving job, and fair enough - they need the money.

The truth, however, is that much of the best of Cape Verde has nothing to do with suntan lotion and holiday novels - a fact I began to fathom on my first day, sitting in a community hall in Mindelo on the island of São Vicente, watching a club demonstration of capoeira, the stylish, slave-based martial art that reflects Cape Verde's links to South America (the technique originated in Brazil). It was an exquisite evening, brought to a poignant close when all 50 athletes in the room turned to applaud their only visitor - me.

Something similar happened the following day in a music shop in the centre of this attractive colonial town where I met guitarists who played passionate local songs in an impromptu concert, including one with the telling title, The Misery of Life. This is the sound of Cape Verde. As one guitarist explained: “We sing about the sea, the blue sky... and the beauty of scarcity.”

Where else would you hear that kind of distorted pride in the links between arid landscape and yearning music? In any case, the songs partly explain why I arrived in nearby Santo Antão feeling a bit queasy, not just from the hour-long ferry ride but also from two sleepless nights: in Mindelo they sing about scarcity into the small hours. What came next, however, blew away all stupor because Santo Antão is one of the great, dramatic landscapes of the world.

Walking down from those jagged volcanic tops into the Paul valley took me by way of ancient, narrow, cobbled paths past lush terraces into silent and isolated villages sheltering at the foot of the mountains. It was eye-burning stuff, all the more surreal because it was silent: there were no roads and no cars for much of the journey.

One or two villages had make-do “cafés” - little more than rooms with views and booze. But there were also guesthouses. The one I stayed in, Casa Das Ilhas, run by three French and Belgian friends, was perched high up, windows filled with views of rock terraces and vast canyon emptiness. Here, I spent the end of that five-hour walking day simply walking some more. The owners outlined a route through sugar fields and packed me off before dinner. And when I got back they laid out a meal of fresh fish and local vegetables, with wine from the fridge and a tumbler of the local, sugar-based grogue. I finally slept.

Santo Antão is the second largest in Cape Verde's sprawling island cluster, its highest mountain almost topping 2,000m. To the west, the land is dry and largely deserted - the entire island is home to only 50,000 people - but in the high northeast where I spent the next three days there are streams, green terraces and lush valleys.

Forget beaches. You'll find one or two, but mostly the big Atlantic waves crash on to stunning rocks and gaunt cliffs. Walking the eight coastal miles from tiny Ponta do Sol to the village of Cruzinha, I was staggered by the sight of tiny villages clinging to minor crevices in cliffs hundreds of feet high. It was breathtaking.

Later I mountain-biked on to high desert plains and stopped with my French guide, André Szpera, at a village house for lunch, where the owner held up an egg and asked in gentle Creole, did I want it fried?

I did other walks, had other adventures. I went canyoning with a Spaniard called Eduardo Gomez who helped me to abseil down waterfalls. I strolled Ponta do Sol's empty streets and felt almost as if this was South America - wide, low-rise and faintly sun-worn.

Going home at last, I stopped on Sal and toured its southern beaches. The island is quickly filling with villas and resorts that will, in the end, turn the place into something that you can see elsewhere. Same with Boa Vista, probably. But some of those other islands, those other landscapes - it's hard to see how they can ever be ruined, or equalled.

Need to know

Getting there Archipelago Cape Verde (017687 75684, www.archipelagocapeverde.com) offers a seven-night trip to Sal, São Vicente and Santo Antão from £1,386pp. The cost includes international and inter-island flights, visa, B&B accommodation and two dinners and three picnic lunches, three guided walks on Santo Antão, a half-day music and culture tour on São Vicente, including a capoeira school visit, and ferry tickets.

Read Cape Verde Islands (Bradt, £13.99).

Climate The temperature is about 25C (77F), year round. The wetter months tend to be August to October.

Flight Six hours from the UK.

Times recommends

• 'New York has lost its edge'
• The UK and Ireland's 25 best Christmas events
• Chalet Chef 2010: the winners