I was told that it’s a cert - just choose the right place in Madagascar and you’ll see some wild lemurs. I had watched the wildlife documentaries and read the guidebooks, but I still didn’t expect it would happen so soon. Day one, in fact, before I’d even unpacked the sun cream.

I was sipping tea in the shade of the veranda in the afternoon, weighing up whether to go for a dip in the palm-fringed pool or in the calm blue Mozambique Channel beyond. I heard a rustle in the trees to my left, and a black-faced lemur sprang into view, its front legs held high as if it had just peeled off from a dance. It leapt and bounced, several yards at a time, to the middle of the lawn, just feet from where I was sitting, then briefly stopped to sniff the air before jumping over to some trees on the right and swinging off into the forest. Remark-ably, there was hardly a stir among the handful of other seasoned diners. Fantastic, leaping lemurs at tea is the norm. Welcome to Madagascar.

I was staying at Hotel Anjajavy, 120km (70 miles) north of Majunga on the northwest coast. There is no main road access to this part of the country, so I had flown up that morning in an hour and a half from the capital, Antananarivo, in a seven-seater aircraft. The arrival is spectacular. We circled the forested peninsula and headed briefly out to sea before turning towards land, passing over the arc of a beach and touching down on a private runway bordered by a wooden fence to keep out any straying zebu (the local cow).

Anjajavy’s South African manager, Hilton Hastings, whisked us away by four-wheel-drive vehicle along a bumpy track to the hotel, which is situated in a 450ha (1,000 acre) nature reserve of dry deciduous forest — the reason why there are so many lemurs close by. I was later told that the lemur I had seen was a Coquerel’s sifaka – one of the largest varieties in Madagascar and distinct from others by their black faces, inquisitive eyes and an unusual “shif-auk” call they make as they leap through the trees.

Anjajavy’s main reception and dining area is in a huge colonial-style building with high ceilings, billiard table and bar, while 25 air-conditioned villas, made out of rosewood and roofed with satrana leaves, line a long, white sandy beach.

Many guests spend their stay lounging around the pool, but there are plenty of activities outside Anjajavy’s secluded grounds. I joined a boat trip along the spectacular coastline to visit some of the undisturbed inlets and a sacred 800-year-old baobab tree, and the following day I kayaked in the mangroves, home to fish eagles and sacred ibis. Fishing, waterskiing and diving are also organised, but what sets Anjajavy apart from other quality hotels is its close connection with the local community.

The hotel employs 75 staff from the village and buys much of its fresh produce from the local fishermen and farmers. In collaboration with an NGO, Ecoles du Monde, the hotel has helped to build and supply equipment for the village school and runs workshops to show how to fish more sustainably.

Hastings clearly has a genuine love for the country and its people. “Madagascar is the kind of place where the locals will try to flog you a pineapple on the street, but if you don’t buy one, they’ll give you one anyway,” he says.

For all its attractions, Madagascar has not traditionally been a favourite with British holidaymakers. Just over a thousand Britons — largely aid workers, volunteers and backpackers — visited the country in 2001. But times are changing. About 2,000 people flew with Air Madagascar from the UK last year, and it is estimated that about the same number flew there on other air-lines via Mauritius, Johannes-burg and Nairobi.

Hilary Bradt, who has been leading tours to the country for 30 years, says: “People used to feel uneasy about travelling around Madagascar because things would go wrong. But now the infrastructure is better, it’s no longer just for intrepid travellers.”

If barefoot luxury is what you want, look no further than the island of Tsarabanjina, the tropical hideaway where Joanna Lumley famously converted her bra into a pair of slippers in her castaway documentary Girl Friday. These days the daily dilemma on Tsarabanjina isn’t where to find fresh water, but whether to choose waterskiing or aqua aerobics, rum punch or piña colada. The island is a 90-minute boat ride from Nosy Be, which can be reached by a 55-minute flight up the coast from Anjajavy.

Tsarabanjina is, perhaps, one marble floor short of five-star quality, but it has recently been bought by the Constance Hotels group, which owns five-star hotels in Mauritius and the Seychelles. The manager of Constance Hotels assured me they wouldn’t be changing much, however, since Tsarabanjina has a loyal following — more than 270 visitors have returned at least three times, and another 300 have been back twice.

Times recommends

• The world's 10 weirdest things to eat
• Correspondents: hoteliers revenge for Tripadvisor
• A slow, ponderous journey up the Mekong