It was my first visit to Kuching, a relatively under-the-radar destination, that easy to become enamoured with. Driving in from the airport, the burgeoning suburbs are serrated with brand-spanking apartment towers and the ensuing contemporary palaver, but the buzzing heart of the city remains resolutely human in scale, evocative and awash in heritage architecture. Sarawak’s historic capital is quite simply one of Malaysia’s most charming and laidback cities, slung around the banks of the Sarawak River, with Mount Santubong brooding on the western horizon.

Before diving into the downtown delights, I joined a sunset river cruise, which serves up a superb introductory overview of the city’s skyline and landmarks, while gliding along the sluggish beige artery. You’ll see brightly painted water taxis (tambangs) doing a brisk trade and intimate perspectives of the traditional stilt houses of Malay kampungs, edging the river. On the north side of the river, statement architecture doesn’t get more ostentatious than the gleaming State Legislative Assembly, lording over the river like a bling-bling golden spaceship. Riverside colonial vestiges include the Square Tower and Fort Margherita, both built in 1879, and the sprawling Astana, formerly residence of the White Rajahs and now home to the Governor.

After admiring a theatrically fiery sunset gild the cityscape, watching dragon-boats slice through the water like knives through butter and marvelling over the on-board traditional indigenous dance performances, I disembarked at the jetty on Kuching’s waterfront, lustily festooned in fairy lights. A one-mile long pedestrian promenade snakes along the waterfront, making for serene and sensory strolls by day and night. Being a tropical country, the sky split open early evening, throwing down a polite shower, or sometimes sheets of torrential rain. Either way, the rainstorm was always welcome, cooling proceedings after the searing heat of the day.

Sarawak’s back-story is indeed fascinating, in which those “White Rajahs” ruled the roost in this trading port for a century. They were a dynastic monarchy of the British Brooke family, who founded and ruled the Raj of Sarawak, from 1841 to 1946. It all began with James Brooke. As a reward for helping the Sultanate of Brunei fight piracy and domestic insurgency, he was granted the province in 1841 and received independent kingdom status. The dynasty continued through Brooke's nephew and grandnephew, the latter of whom ceded his rights to the United Kingdom in 1946. The last legal heir, Anthony Brooke, actually died in New Zealand in 2011. Their paternalistic rule of Sarawak is still regarded favourably by the locals today, because the Brookes pursued a policy of protecting the indigenous people from exploitation.

Following Japanese occupation during WWII, Sarawak eventually became part of Malaysia in 1963. Up early the following morning, the day had dawned bright, warm and fresh, as I gazed across the waterfront from the primo location of the Riverside Majestic Hotel. Suitably fuelled up after devouring a heaped plate of Nasi Lemak for breakfast, I met my effervescent local guide, Tony, who had a smile as bright as the moon. I remarked to Tony how impressively clean the streets were, devoid of any eye-jarring litter. He observed that the city has two Mayors, offering a sense of healthy competition as to what part of the city is the cleanest. Over the course of several hours, Tony whisked me through the compelling historic core of Kuching, a true melting point of culture and religion, where Christianity, Buddhism, Hinduism and Islam happily co-exist.

We popped in to the exquisite Tua Pek Kong Chinese temple, wafting in incense, marvelling at the masterly craftsmanship of this pint-sized temple. Parallel to the waterfront runs Main Bazaar Street, brimming with shops selling authentic tribal handicrafts. Merrily painted in a rainbow of faded colours, these storied Chinese shophouses pepper the old town, row upon row of them, redolent with charm and time-honoured trading verve. Chinatown’s back streets and lanes form a honeycomb of incense-filled temples, cafes, street food stalls and miniature workshops abuzz with tinsmiths, cobblers, carpenters and tailors. The aptly-named Carpenter St is a revelation in old-school craftsmanship, as old-timers ply their specialist trades, kerbside.

I perused a feast of colonial landmarks from the Brookes dynasty, including the elegant Old Court House with colonnaded terraces, which has become a culture hub. One venue not to miss is Sarawak Museum, which has barely changed since it first opened in 1891, with a rich collection of local flora and fauna, and vivid insights into the indigenous tribes of the Borneo rainforest. Kuching means “cat” in Malay and you’ll notice cat statues all over the town centre – catnip for Instagram! There’s also the Cat Museum, devoted to all things feline. It is the world’s oldest cat museum and bulges with a staggering array of exhibitions devoted to the history and abiding love affair with pussy-cats. There are over 4000 exhibits!

Passing through Merdaka Square, the Sunday morning service was just wrapping up at the gorgeous cream-hued St. Thomas Cathedral. The golden-domed City Mosque is another uplifting house of worship, just a short walk from the open-air market, which was popping with colour, energy and hustle. Old men manned souvenir street stalls while also guarding briefcases curiously stocked with a vast selection of sex performance and anatomical enhancements. Adding to the carnival of colour, bubbling pots and sizzling woks served up all manner of local culinary delights, which I was itching to sample. Kuching is an irresistible foodie paradise, particularly the street food, where most dishes cost less than a NZ$2-3.

I absolutely adored Chinatown’s Seng Kee, a hawker-style food court, where there’s a choice of fishball soup, pork satay, Sarawak Laksa, Chinese rice porridge with salted egg and preserved vegetables, or for the extra-intrepid, kueh chap, a concoction of slow-braised pork ribs and intestines. I plumped for Sarawak Laksa, which may well be the best Laksa I have ever had. The Sarawak broth is made with a mixture of sambal belacan, sour tamarind, galangal, lemongrass, coconut milk and herbs and spices. The laksa comes with egg strips, prawn, chicken slices, bean sprouts and lime garnished on top of the mee hoon.

This creamy texture and mix of spicy and sour tastes pack a particular punch thanks to Sarawak’s famed peppercorns, plus it comes topped with tiny calamansi limes. In nearby Padungan Road, queues are a constant for Noodle Descendents which serves an awesome bowl of kolo mee, the favourite local dish of minced pork and noodles, served by a tiny lady who’s been cooking here since 1957. Later that night, Tony led me to Top Spot on Bukit Mata Street, an immense open-air seafood court on the roof of a car park. More than 500 diners sit at communal tables, ordering from neon-lit seafood stalls displaying live crabs, prawns, razor clams, wriggling squid, grouper, pomfret and parrot fish. Dine like a local!

Also on the foodie trail, the rediscovery of indigenous Sarawak cuisine is on-trend and a stellar specimen is the.Dyak on Simpang Tiga Road. Dishes include manok lulun (chicken stewed in bamboo with tapioca leaves and herbs), while the vegetables are headlined by midin (wild ferns). Paku Midin is the Queen of the jungle Ferns in Sarawak, which I fast fell in love with. On the north side of the Sarawak River, a steady stream of tambangs whisked people across to the cheerfully-coloured village of Kampung Boyan, to get their fill of Kek Lapis from the Mira Cake House. These brightly-layered cakes have now evolved into hundreds of designs, textures and tastes. They’re delicious, moist, buttery – and instant eye-candy! A sure-fire way to beat the sticky heat of day is to savour Ais Kacang, Sarawak’s shaved ice dessert.

The bowl of ice is topped with a kaleidoscope of goodies, piled high with jellies, ice cream, condensed milk, fruits and colourings. Tapioca pearls pop in the mouth, chunks of fruit release their sweet juices, ice crunches and the whole thing swims around like a liquid disco. Finally, you know you’re in Malaysia when those addictive, sticky skewers of meat, sizzle from street stalls with seductive temptation. I certainly enjoyed my fill of satay on the streets of Kuching! The city’s table is a generous one, go hungry, tuck into everything and discover their delights. http://www.malaysia.travel/en/nz

Fly Business Class with Malaysia Airlines and revel in their famous “satay trolley”, wheeled out to mouth-drooling guests after being faithfully prepared over a real charcoal grill. Fly to Sarawak with Malaysia Airlines, who offer multi-day services between Kuala Lumpur and Kuching, for the 90 minute flight. Malaysia Airlines flies direct to Kuala Lumpur from Auckland with convenient overnight flights. www.malaysiaairlines.com

Make plans for your own flavourful Kuching Adventure with Wendy Wu Tours. Their five night private tour, with local English-speaking guides, includes the cosmopolitan delights of Kuching, traditional cultural experiences and encounters with Borneo's revered orangutans. www.wendywutours.co.nz