Arrive at Sanur Beach, Bali. Meet your tour operator and the guest expert Jeffrey Mellefont. From here, travel by bus to a port on Bali’s scenic eastern coast. This is a pleasant and beautiful drive and a great opportunity to see a little bit of the island. After boarding a handsome, traditional, timber, ‘pinisi’ boat, have a chance to settle into your cabin and meet the other passengers and crew before enjoying the first alfresco meal on the main deck. The operator briefs you on all the activities and safety aspects of the cruise at this time. Then set off on the first leg of the voyage, which takes you north into the Bali Sea while the majestic cone of Bali’s sacred volcano, Gunung Agung, recedes astern.

By the time the first tropical dawn breaks, you have reached the Java Sea and the remote Kangean Islands. This archipelago, stretching 85 kilometers from east to west, is your maritime playground over the coming days. Its population is a nautical melting pot because it lies at the crossroads of the Java, Bali and Flores Seas, and the Straits of Makassar. The first landing is on Seppeken Island, the administrative center of the eastern Kangean Islands. Walk easily around this island in 45 minutes. There’s a rare fleet of sail-powered outrigger fishing boats here called ‘perahu pakur,’ and the larger ‘perahu lete’ with their big lateen sails. Return for lunch on board before sailing to Little Pagarungan, a typical Kangean maritime community on a flat, clean, sandy, palm-shaded island. Local traders visit to load fish on ice, or coconuts, for markets as far away as Kalimantan (Borneo). Today share a traditional meal at the home of a famous boat builder.

Depending on tides and winds, visit a reef-dwelling Sea Gypsy village built on stilts over coral. Alternatively, land on Little Seridi Island, a remote white-sand cay that dazzles you with the emerald or sapphire hues of its clear waters. With no cars on its sandy roads, a stroll across the island is leisurely, peaceful and friendly. It is home to migrants from Buton in Sulawesi, their tidy households and mosque shaded by nodding coconut palms. Relaxing on the verandah of the village head, learn about their origins and their island lives and lifestyle. By the afternoon anchor off Saur Island, where pretty villages and white-sand beaches line the shores and where you can go ashore and meet beachcombing people who rarely, if ever, receive foreign visitors. Their frank, friendly demeanor delights you. This is also one of several places where you can snorkel.

The captain weighs anchor before you awake to head west to the largest island and the one that gives this remote group its name: Kangean Island. Round Saubi Island, most of which is a nature reserve with extensive mangroves, coasting close to Kangean’s shores and past a shipwreck that sailed too close! Pass bays and isolated hamlets below a long, jungle-covered ridge that’s famed for its forests of teak – the tough, durable timber favored by boat builders. Today’s landing place is Batu Guluk, the main port for the largest of this island group. Travel in a local mini-bus fleet to Arjasa, the main town, where a few heritage Dutch colonial buildings still survive. Here witness tamratan, the unique local cultural tradition of dancing horses, which are called upon for ‘rite of passage’ ceremonies such as weddings and circumcisions. En route to the wild northern sea coast, visit the extensive underground complex called the Cave of the Yellow Princess, and learn of its sacred significance and legends amid the ancient stalactites and stalagmites.

Having cruised overnight from the Kangean Islands, anchor off at the major port of eastern Madura Island. The approach is through an ocean dotted with spectacular bamboo fishing platforms. Madura, the Bali-sized island close to northeastern Java, is the home of a hardy, wide-ranging seafaring culture whose traditional sailing craft or ‘perahu’ were always the most colorful and unusual in all of Indonesia. The nearby regional capital of Sumenep was the seat of ancient ruling sultanates as well as the Dutch East Indies Company. Hugely prosperous in the eighteenth century, the city is now a quiet, peaceful backwater, yet its past glory is still in evidence. Visit the 18th-century Kraton (sultan’s palace) with its unique architecture, harem bathing pools, and museum loaded with royal heirlooms. Here be welcomed with cultural performances staged especially for you. The nearby 18th-century Grand Mosque features multicultural architecture – Portuguese, Dutch, Indian and Chinese – as do the picturesque Asta Tinggi royal grave sites. Before returning to the ship linger for the start of the night market at the ‘alun-alun’ (town garden/square) and ride the extraordinary ‘odong-odong’ – fanciful and fantastic joy-ride vehicles like nothing you’ve ever seen!

Next morning your taxi fleet drives us up to Madura’s north coast to view the amazingly decorated, traditional fishing fleet of big, teak-built ‘selerek’ (‘seine net boats’) that line the banks of the palm-shaded river ports of Ambunten, Pasongsongan, and Pasean. These may well be the world’s most spectacular fishing boats. They’re decorated with a vibrant artistry of carvings, paintings, ornaments, and bunting that’s hard to believe, incorporating symbols and imagery drawn both from high, courtly traditions and robust folk styles, featuring religious themes as well as pop culture. On the way back to the ship, relax for lunch, pony rides, or swimming at Slopeng or Lombang, your choice of clean, local, ocean-beach resorts. Don’t be put off by the term ‘resorts’: these are unsophisticated and unspoiled, for simple local recreation and family visits on holidays and holy days.

An overnight passage from Madura brings you back to Bali’s Pulau Menjangan, where you moor in the waters of the West Bali National Park, renowned for its diving and snorkeling. This is in the northwest corner of Bali, so from here cruise during daylight hours so that you can enjoy the spectacular scenery as you coast along Bali’s northern littoral. The voyage continues through the night to return to Benoa Harbour near Sanur where the journey started, to have you ashore by the following morning.