Dawn had not yet broken when we trooped sleepily up to the bridge of the Aranui, high above the ink-black waters of the South Pacific. Captain Theodore Oputu didn't even move his head to acknowledge us. His hands were on the ship's wheel and his eyes bored into the void of Baie de Vaipaee, the so-called "Invisible Bay", on the Polynesian island of Ua Huka in the remote Marquesas.
The moon was still high when daybreak's scarlet finger began to tear back the night, dawn slowly revealing an inlet as narrow against the towering volcanic rocks as the blade of a hunter's axe. There were jagged cliffs either side and snow-white surf pounded against them. Somehow, Captain Oputu had to manoeuvre 8,000 tons of cargo vessel into this crack dead ahead and then swing the 117 metres of the Aranui in a complete 180 degree turn so the bow faced the way it had come. Some trick.
He had just 30 metres of clearance from the rocks each side and four fathoms of leeway on the bottom. Hairsbreadth stuff. The last time any captain other than Theodore tried this he was on the bridge of a French Naval Frigate, and holed the hull. It was the prospect of disaster that had brought almost all of the Aranui's 150 paying passengers up here when they should have been in their cabins asleep. The ocean's swell lifting and lowering the ship in a heaving sea as if it was a toy boat, seemed to herald a "Mayday".
Captain Oputo didn't look like a nautical hero. He wore flip flops, jeans and a T-shirt with 7Up across the front. When the passengers in shorts, digital cameras around their neck, came right onto the bridge to look at the charts and peer at the neon-green radar screen, he calmly carried on with his orders... lower anchor (for extra drag), operate bow thrusters (to help turn the ship), drop the deck hands into the whaler (so they can quickly tie hawsers onto the rock face to hold the ship), let the wind catch the stern (to help push it round). And as if on an invisible turntable, the Aranui slowly revolved full circle onto its handkerchief-sized berth.
Then a funny thing happened. The passengers started to clap - they all knew this docking was one of the most extraordinary spectacles they had ever witnessed. Captain Oputu smiled shyly. There could be no more thrilling introduction to voyaging through arguably the most exotic seas on earth to some of the most remote specks of land on the planet. The Marquesas, discovered by the Spanish in the 16th century, are 11 lonely, wildly beautiful islands, half of them uninhabited; volcanic upheavals thrust from the ocean, clothed in velvet jungle - all steep valleys thick with palm, banana, and mango, watched over by lordly mountain peaks. They have no coral reefs so the waves roll uninterrupted, in great foaming breakers, all the way from South America, 6,850 kilometres to the west.
It was to one of these islands, Hiva Oa, that Gauguin fled civilisation to paint masterpieces of sultry wahines. He fathered numerous children (in one week I met two of his descendants who both proudly showed me copies of paintings the old roué had created of their great-great-grandmothers) and is buried under a gardenia tree on the slopes of the local cemetery. His grave is only a few feet from that of the French singer Jacques Brel, who retreated here in the late Seventies dying of cancer and wanting to end his days in an earthly paradise. Herman Melville, author of Moby Dick, also jumped ship in nearby Nuku Hiva and was trapped by a tribe of cannibals, before escaping to write Typee, the best-selling novel based on his capture.
Indeed, as recently as 40 years ago, the Marquesans were ready to kill for their primitive beliefs. Explorer Thor Heyerdahl was driven into the hills of Fatu Hiva when he was caught digging up a sacred place for Tikis, the natives' unsettling statues of the gods, releasing, they said, the tupapaus, evil spirits that lie sleeping until disturbed. He only survived by boarding the first ship he saw. Paul Theroux thinks Fatu Hiva the most beautiful island in the world. "It's the emptiness, the way daylight plunges into it only to be overwhelmed by the darkness of its precipitous valleys and the dangers of its shoreline that give it the look of a green castle in the sea," he writes inThe Happy Isles of Oceana.
There are almost no roads on these islands and the only vehicles are heavy-duty four-wheel drives. The Marquesas are 1,480 kilometres from Tahiti and there are few flights to the one or two landing strips, almost no hotels. But once every three weeks, the white hulled Aranui sails out of Tahiti's Pape'ete harbour on a 16-day voyage delivering vital supplies to the natives of six islands. It is a lifeline to the Marquesas. They ship back copra - dried coconut kernal - and noni, the juice of the Indian mulberry, which is transported to America to be made into a fashionable health drink.
The Aranui is one of the few cargo vessels of its kind in the world that takes passengers, and the only ship to the Marquesas. Once, you had to sleep on the deck. Now there are grandly titled "state rooms" on the top deck and dormitories several decks below. My twin-berth cabin was on B deck, just above the waterline. Great in fine weather, but when rough it was like living in a washing machine as the sea swirled around the porthole. Every morning we sailed to a new island and tied up to await the day's shore visit. American matrons, wealthy Parisian industrialists and British students leant over the rail together in an egalitarian way, to watch muscular seaman guide swinging crates on wires from the ship's cranes onto primitive docksides.
I had wanted to visit French Polynesia all my life, ever since, as an eight-year-old swapping stamps in a freezing boarding school dormitory, the images of palm trees and lagoons imprinted on those small perforated dots of paper, seemed to offer a life beyond Latin prep. But they were of Bora Bora and Morea - backdrop for Mutiny on the Bounty-type films, with majestic saw-toothed mountain peaks that swept down to surf-splashed coral reefs. The Marquesas have only black-sand beaches and few of them. Their seas teem with sharks, and the islands have an arrogant grandeur, that makes no immediate effort to seduce.
The few Polynesians who live here appear to inhabit a world half a century behind the rest of us. And I suppose that is their charm. The islands are wild and empty, the people vulnerable, taking an almost childlike pleasure in meeting strangers. Only 671 people live in Tahuata and only 100 in its main village Hapatoni. You can only get there by boat. There is no dock, so we landed in whalers that looked like the boats the troops hit the Normandy beaches in on D-Day. When we arrived, there was an all-women ukelele band playing and giggling children ran forward to drape beautiful garlands of hibiscus around our necks. Then we walked down a grassy path lined with 100-year-old tamanu trees, to a feast of wild pig cooked in an earth oven, while we watched an intimidating Haka war dance, and later hunted for exquisite wood carvings. The women were still playing their hand-made ukuleles as we left.
It's all very well seeing these islands from the ship - I kept thinking of Captain Cook, the first Briton to set eyes on them - but the only way to truly experience them is to put on your boots and hike. That's the best way to see the mysterious remains of the Tikis, half hidden under the jungle's greedy green tentacles. The petroglyphs at Lipona on Hiva Oa are more alarming than the Easter Island statues. There is one of a turtle and a man mating.
On Fatu Hiva, 20 of us tramped the 17 kilometres from the harbour at Omoa along cliff-top paths, through two lush valleys, home only to herds of wild horses, to the phallic peaks along the skyline of Hanavave Bay, christened by natives "the Bay of Penises". Outraged missionaries re-christened it "the Bay of Virgins". When we set sail at sunset it was drenched in purple and the surrounding peaks threw off a dazzling bronze reflection. Religion, superstition and sex are entwined here like creepers around a banyan tree.
Nothing can shake the conviction of the people here in the supernatural. Outside a fine new Catholic Church in Nuku Hiva, I was shown a cross with the crucified Christ on one side and a giant penis on the other. The Marquesas are the islands of men, we were constantly reminded. But only by the men, of course. On another island, an American nurse recounted the disquieting story of a local woman who cut her foot on a stone stolen from a marae, refused to be treated for gangrene because she believed this was the Tikis showing anger, and quietly accepted death.* *You do not find this sense of primal power in the Marquesas' more glamorous French Polynesian sisters, Tahiti and Bora Bora. Though stunning, they are being colonised by luxury American hotels that command choice beach-front real estate. On one of our hikes, a German teacher told me that on her holidays she always felt "superfluous". But in the Marquesas she didn't because she was contributing to an ideal; to islanders who had chosen to reject life in the developed world to continue their ancestral traditions in a landscape that hadn't changed in aeons. It was a provocative point.
The writer flew to Tahiti with Air New Zealand (0800 028 4149; www.airnewzealand.co.uk) from Heathrow via Los Angeles. Returns start at £941. Air Tahiti Nui (0870 066 2050; www.airtahitinui.co.uk) also flies to Pape'ete, Tahiti from Paris via Los Angeles.
To reduce the impact on the environment, buy an "offset" from Climate Care (01865 207 000; www.climatecare.org). The environmental cost of a return flight from London to Tahiti, in economy class, is £37.20. The money is used to fund sustainable energy and reforestation projects.
Twelve-day voyages of the Marquesas aboard the Aranui III (00 689 426242; www.aranui.com) start at €2,910 (£2,079) full board in a standard A-class cabin. The price includes all excursions. The Aranui can take up to 200 paying passengers in 10 suites, 12 deluxe and 63 standard cabins.
Informative lectures are given each night by knowledgeable local guides about the islands to be visited the next day. The Pearl Lodge Hotel, Nuka Hiva (00 689 50 84 53; www.pearlresorts.com). Bungalows start at 19,980 Pacific Francs (£115), room only.
Tahiti and Her Islands: 020-7202 6378; www.tahiti-tourisme.co.uk.