"I hope you like my boat," said Sergio, the co-owner of the Agua Hotel in Cartagena, as he ushered us through the heavy front doors to the taxi waiting outside. I was bound for one of the city's two marinas, where his vessel awaited my arrival. (Once under way, I had to resolve the small problem that neither the driver nor I knew which one I was supposed to be heading to.)
This year marks the 200th anniversary of Colombia's declaration of independence from Spain – and the celebrations are likely to be prolonged. Cartagena itself has undergone a revival over the last few years, establishing it as one of the most beguiling destinations in all of the Caribbean.
So beguiling, in fact, that I was leaving town very reluctantly. The Agua itself is stunning, a 17th-century mansion that Sergio and his partner Gustavo have transformed into somewhere that is both their home and an exquisite five-room hotel. It sits – with no sign to announce it – deep inside Cartagena's Old City. Honeymooners could easily remain in the sophisticated embrace of the Agua for days, browsing in its indoor courtyard, or collapsing by its sapphire-tinted roof pool as white-uniformed staff keep the cocktails flowing. They'd probably brave the outside world just once a day for a couple more drinks at the Café del Mar on top of the city's ramparts at sunset, before progressing to one of the city's many tremendous restaurants.
The best known of these is La Vitrola – and to snag a table you are likely to need the help of your hotelier. Occasional diners here have included Fernando Botero, Colombia's best-regarded living painter and sculptor (rip-offs of his work cram the shelves of every Cartagena souvenir shop) and the country's equally venerated writer, Gabriel García Márquez, who actually lives mostly in Mexico. However, while the place vibrated with live Cuban jazz and the chatter of the self-regarding patrons, when I visited the food was only so-so.
An alternative evening's itinerary might begin with the high-ceilinged bar at the Sofitel Santa Clara Hotel, once a convent and now a place with more bustle than the Agua, as well as a full-sized pool and a tame toucan in its gardens. In the square just outside the hotel sits the Juan del Mar restaurant, which is apparently renowned for seafood.
In fact – like the marinas – there are two Juan del Mars. They face each other on the square. The first is advertised as a people-watching hot-spot; the other, though it offers a transporting menu of Peruvian specialities, has the feel of an Andean grandmother's front room. I found myself in the latter, thinking I was in the former and wondering what constituted people-watching in Colombia, as there were no other diners.
My happiest culinary discoveries came later in my stay, after I had returned to Cartagena from my adventures on Sergio's boat and the Tayrona National Park (of which, more later). In slightly more parsimonious mode I was lodging in a still more intimate hotel – this time with just three rooms – called the Casa Carretero. It lies in Getsemani, a neighbourhood adjacent to the Old City. Here the churches are a little humbler and the streets a bit narrower. The cruise ship crowds (yes, they dock in Cartagena) generally don't venture to Getsemani, but that is their loss.
It was while in Getsemani that I visited the Café Havana. Packed with tourists and locals downing beers and mojitos, shouting gossip and swaying to a live band, this late-evening haunt instantly sparked memories for me of a visit to the capital of Cuba. Like Cartagena, Havana is a city that many travellers pass by. They are put off – or, in the case of Americans, impeded – by politics. Visit Colombia and friends will interrogate you about safety.
The civil war between the Farc Marxist guerrillas and right-wing paramilitaries as well as government forces is not over quite yet, even though the violence and the kidnappings have ebbed very significantly since Alvaro Uribe became President in 2002. And Colombia is still the world's leading exporter of cocaine. But most of the country, and certainly the Caribbean coastline, as well as the central parts of the capital, Bogotá, are considered safe for tourists these days. Still, after dark a little caution is advised: don't drive countryside roads or venture too far from areas where tourists assemble.
Tangled national politics and colonial architecture apart, Havana and Cartagena have other things in common, including large helpings of rum, music and dance. Walk the streets of this city and the cafes are bursting with vallenato, the beat of Colombia's Caribbean coast, a style of salsa but with the notes of an old German accordion driving the melody.
Cartagena isn't about sight-seeing in the traditional sense. A trip to the Convento de la Popa a few miles outside was marred by a rascal of a taxi driver who attempted to multiply my fare 10 times (a dispute that was resolved only when I proposed a policeman's mediation) and was worth doing only for the great views of the city and port. Nor, I should warn you, are the beaches here anything to get excited about. Indeed, during my stay the sea was so wind-whipped it had a hue more of Bexhill-on-Sea than Barbados.
Mostly, this a city built for strolling. If you tire of the bougainvillea-draped wooden balconies, distract yourself by counting how many different kinds of decorative door-knockers you can find. Hang out in the Plaza Simon Bolivar, where most likely dancers and musicians will be performing in the small park, or take a coffee or a beer in the Plaza de San Pedro Claver just to survey the passers-by. A dinner at the Restaurant San Pedro was made more enthralling by the spectacle of guests arriving for a high-society wedding in the church opposite that gives the square its name.
For craft shopping, go to the line of cave-like shops clawed out from the walls of the ramparts at Bovedas near the Santa Clara. Beware the cruise-ship crowds, however, and those curvaceous faux-Botero paperweights and bookends that seem to multiply like rabbits.
Now, though, I was speeding out of Cartagena, having successfully tracked down the Agua in the correct marina. This sleek and sexy motor launch had room for 10, but there was just the captain and his mate for company. We headed past the shockingly modern skyline of Bocagrande, the L-shaped sliver of land crowded with high-rises where most wealthy Colombians prefer to stay and play when they visit the city. Next came a pair of 18th-century stone-and-brick forts built by the Spanish, who were tired of the repeated sea-borne sieges of Cartagena from pirates and plunderers (Sir Francis Drake among them). V C Slowly, the sea acquired the colour you would expect of the Caribbean, and the mangroves of the shore began to surrender to slivers of white-sand beach. We were approaching the island of Baru, one of several contained in the Corales del Rosario national marine park. It lies 45 minutes south-west of Cartagena (in our boat at any rate).
If the Agua back in the Old City offers sensual calm, its sister property here is all about languid luxury. There are just three thatched-roof casitas – though a few more are planned – and two have their own private pools. These may be on the small side, but perched as they are high above the ocean below, they speak of impossible indulgence.
The path to your casita is rather steep and long. But before you walk it, you are invited first to take everything in with a glass of mint-water either at the boat jetty, which has sun recliners and steps down for a swim, or at the raised lounge and dining area, itself under a huge span of thatch.
The sea here is of a colour you are unlikely to have seen before, as if icing sugar has been suspended in the turquoise to turn it milky green, and is dotted with barrier islands and hidden beaches. Ask the Agua staff and they will take you on a smaller boat to one such beach for a day – or just an hour – of Robinson Crusoe solitude.
Privacy seemed to be guaranteed, until a man appeared selling necklaces and bracelets. He had paddled over on a broken boogie board; I felt obliged to buy.
To return to those honeymooners once more, it would be hard for them to beat Agua Baru as a destination, which mimics, and even improves upon, the remotest islands of Thailand or the Philippines. The only mild caveat would be the cacophony of birdlife that erupts with sunrise. It is so loud that I was told one recent visitor to the property asked for it to be turned down for the rest of his stay.
After two days in my Baru idyll, I returned to Cartagena for the four-hour drive north along the coast towards the border with Venezuela. I travelled past the large industrial port of Barranquilla (where the singer Shakira comes from) and towards Santa Marta and the Sierra Nevada mountain range that looms behind it. Where the mountains dive into the ocean you will find Tayrona National Park, which I intended to explore the following day.
First, though, I had to find the Koralia Beach Hotel, which had been recommended to a friend of mine by Shakira herself. Expect hippy/crazy, he'd said, but you will love it. I can't argue with any of that.
Run by Patricia Nieto and her brother Pierre, the Koralia consists of a collection of funkily decorated bungalows by a wide deserted beach. From the shore, on a clear day, you can see the snowy peaks of the Sierra. Most meals here are vegetarian – and you take what you are given (Patricia not long ago travelled to Tibet to convert to Buddhism). On my second day I shared the Koralia with 30 yoga types who'd assembled for a mini convention that had something to do with sun-spots and their mood-swings.
I could have done without the intelligence offered by the hotel's otherwise world-class massage therapist, Dani, about the occasional intrusion on to its grounds of very large boa constrictors. My thatched bungalow was charming but significantly less creature-proof than the casita on Baru.
I left the yoga group to their solar scholarship and squeezed into a little Fiat belonging to Bernardo, a Colombian with a white beard and wiry body. Bernardo had, he told me, lived with his French wife and expanding clutch of children high in the Sierra among the indigenous Indians for 17 years. They'd belonged to a commune of like-minded souls that finally expired in 2000 when the civil war overran it. All the homes, including Bernardo's, were burned to the ground. These days he makes money taking Koralia Hotel visitors into the park and selling them crafts.
Until recently, much of Tayrona was a war zone. In 2003, eight foreigners were kidnapped by guerrillas, and three of its directors have been killed in alarmingly quick succession. Today, these dangers seem to have receded, so much so that the government is promoting tourism in the park. After one day with Bernardo, I understood why.
He had insisted I get up early enough to be at the park's entrance by 8am: opening time. The trek he had in mind would take eight hours, much of it ascending a narrow roadway of ancient stones laid by pre-Columbian Indians. The path rises steeply through the equatorial rain forest to Pueblito, the remains of a city that used to throng with Kogui Indians until the arrival of the Spanish. There is little left now beyond a few stone terraces, but it is the getting there that counts.
At Pueblito we paused to eat soggy tuna sandwiches before descending a different path through the forest, tagged by a group of Canadian and German backpackers who hadn't grasped that Bernardo was experimenting with a route he'd never taken before. We emerged on to one of the many hidden beaches that fringe Tayrona Park. With palms offering shade and huge, surf-smoothed boulders on short promontories, it is among the most bewitching shores I have ever seen.
As I travelled back towards Cartagena – the journey interrupted by one burst tyre and several military road blocks – I contemplated a stay in Colombia that had delivered a perfect combination of new food, new levels of indolence, new friends and just one day of strenuous exercise. And I had been introduced to Cartagena, surely the most stunning city in all of the Caribbean. (Well, except for Havana, perhaps.)
Travel essentials: Colombia
You can reach Cartagena from Heathrow via Madrid and Bogotá with Iberia (0870 609 0500; iberia.com) or via Miami with American Airlines (020-7365 0777; americanairlines.co.uk).
Agua Hotel, Cartagena (00 57 5 664 9479; hotelagua.com.co). Doubles from US$299 (£199), room only.
Sofitel Santa Clara, Cartagena (00 57 5 650 4700; sofitel.com). Doubles from £177, room only.
Casa El Carretero, Cartagena (00 57 300 660 4475; casaelcarretero.com). B&B from US$265 (£177).
Agua Baru, Corales de Rosaria (00 57 5 664 9479; hotelagua.com.co). Double rooms from US$376 (£251).
Koralia, Playa Koralia (00 57 310 642 2574; koralia. com). Doubles from 418,000 pesos (£129), full board.
Eating & drinking
La Vitrola, 1-2 Baloco, Cartagena (00 57 5 664 8243).
Juan del Mar, Plaza San Diego, Cartagena (00 57 5 664 2782).
Café Havana, Calle Media Luna, Cartagena (00 57 310 610 2324; cafehavanacartagena.com).
*Colombia.Travel; 00 57 1 427 9000