Malaysia 3-Week Itinerary: Kuala Lumpur, Borneo, Perhentian Islands & More

AsienMalaysia
Written By Marcel Heizelmann

The rooftop pool view from our hotel in the city center of Kuala Lumpur

The complete honest guide: from orangutan jungle treks to turquoise island beaches, planned by someone who actually did it.

We almost didn't book Malaysia. It felt complicated, too spread out, too many regions, too much planning. We spent weeks trying to piece together a route that actually made sense. Then we went. Three weeks later, standing knee-deep in the South China Sea on the Perhentian Islands, sunburned and still smiling from a morning spent watching wild orangutans in Borneo, we couldn't believe we'd hesitated.

Malaysia is one of the most diverse countries we've ever travelled through. Within a single trip, you go from the glass towers of Kuala Lumpur to silent rainforest trails in Borneo, from the colonial streets of George Town to some of the clearest water you'll ever snorkel in. No two days look the same.

This guide is everything we learned: the route, the timing, the practical stuff, and the honest details nobody told us beforehand. So you can skip the weeks of planning and just go.

Our 3-Week Malaysia Route at a Glance

Here is how we structured the trip, and why it worked:

  • Day 1–4, Kuala Lumpur: Petronas Towers, street food, Batu Caves
  • Day 4–10, Borneo (Kuching): Semenggoh orangutans, Bako National Park
  • Day 10, Kota Bharu: Overnight stop and transit
  • Day 11–15, Perhentian Islands: Snorkelling, beach, total switch-off
  • Day 15–19, Langkawi: Island landscapes, mangroves, cable car
  • Day 19–21, George Town: Street art, Penang food scene
  • Day 21–22, Kuala Lumpur: Final night, depart

Each destination gets its own detailed guide, links below. But first, the essentials.

Why Malaysia?

Malaysia rarely gets the spotlight that Thailand or Bali do. Honestly, that's part of what makes it so good. The beaches are less crowded, the wildlife in Borneo is in a completely different league to anything else in Southeast Asia, and the food culture rivals anywhere in the world.

If you're looking for real variety without a huge budget, Malaysia is hard to beat.

Best Time to Visit Malaysia

This is the question that took us the longest to figure out, because Malaysia doesn't have one monsoon season: it has two, on opposite coasts. Get the timing wrong and you could land on a closed island or in a week of solid rain.

Here is how it breaks down:

West Coast (Kuala Lumpur, Langkawi, Penang / George Town)

Best months: November to April

The west coast is at its driest and sunniest during this window. Humidity is lower, beaches are calm, and sightseeing is comfortable. If your trip centres around KL, Langkawi and Penang, this is your window.

East Coast (Perhentian Islands, Redang, Tioman)

Best months: March to October

The east coast is hit hard by the northeast monsoon from November to February, so hard that most island resorts and boat services shut down completely. The Perhentians close completely. Don't risk it.

We visited in September and October, which turned out to be the sweet spot: the east coast was fully open with clear water and calm seas, while the west coast was warm and dry. It's one of the few times in the year where both sides align.

Our honest take: If you're planning a route like ours that combines east coast islands with west coast destinations, September–October or March–May are your best bets.

Borneo (Kuching, Bako, Semenggoh)

Best months: March to October

Borneo is tropical year-round and some rain is always possible, but the drier months make a real difference for jungle trekking and wildlife visibility. We visited in this window and found trails accessible and wildlife activity noticeably higher.

Practical Travel Information for Malaysia

Getting Around: Fly Between Regions

Malaysia is large and the regions are far apart. Trying to do this trip overland would eat a week of your time. We took 6 domestic flights, and it was by far the best decision we made. AirAsia dominates domestic routes and tickets are cheap, often €20–40 per leg if you book in advance.

For getting around Kuala Lumpur: download the Grab app before you land. It works like Uber, covers the whole city, and saves you from any taxi negotiation. We used it for almost every journey that wasn't walkable.

Getting There: Etihad Stopover in Abu Dhabi

We flew Munich via Abu Dhabi with Etihad, and if you're considering the same route, the stopover programme is worth looking into. We added two nights at the Grand Hyatt Abu Dhabi for around $250 total. For a five-star hotel, $250 is hard to argue with.

We used the two days well. The Louvre Abu Dhabi was one of the more impressive museums we've visited anywhere, the Sheikh Zayed Grand Mosque at sunset was exactly as spectacular as every photo suggests, and we spent the rest of the time at the pool recovering from the flight. It turned a long-haul connection into a mini trip of its own.

If you're flying Etihad from Europe, check the stopover hotel rates before booking a direct connection. The savings on the hotel often more than offset any extra flight cost.

Currency

Malaysia uses the Malaysian Ringgit (MYR). At the time of our trip, roughly 5 MYR to 1 EUR. Cash is useful for markets and smaller restaurants; cards are widely accepted in cities and larger hotels.

Language

The official language is Malay, but English is widely spoken in cities, tourist areas, hotels and most restaurants. We never had a communication problem anywhere on this trip.

What Did Malaysia Cost Us?

Malaysia is affordable compared to Singapore or Western Europe. As a rough guide based on our experience:

  • Budget traveller: €40–60/day (hostels, street food, local transport)
  • Mid-range: €80–120/day (comfortable hotels, sit-down restaurants, activities)
  • Higher comfort: €150+/day (boutique resorts, private tours)

The Perhentian Islands and Langkawi tend to be slightly pricier than the mainland, but still reasonable by European standards.

We tracked our actual costs via Splitwise for the full trip, 22 days and two people, with the real numbers:

  • International flights: €1,365 total / €682 per person
  • Domestic flights (6 legs): €429 total / €215 per person
  • Hotels: €1,269 total / €635 per person
  • Daily expenses (food, drinks, activities, cash): €1,425 total / €713 per person
  • Total: €4,488 / €2,244 per person

That works out to around €102 per person per day all-in, including international flights. Without flights, it's closer to €61 per person per day on the ground, which felt comfortable at a mid-range pace.

Hotel costs include Kuala Lumpur, Kuching, Kota Bharu, the Bayou Hotel in Langkawi, Tuna Bay on the Perhentians and the G Hotel Kelawai in George Town. Daily expenses cover everything paid by card or cash on the ground: meals, drinks, activities, tips, local transport and market purchases.

Internet & eSIM

Mobile coverage in Malaysia is good, even in areas that surprised us like parts of Borneo. Instead of buying a local SIM card at the airport, we used a Holafly travel eSIM. Instant activation before you leave home, unlimited data, no physical card to swap, and it worked from the moment we landed.

👉 [Check current prices here](INSERT HOLAFLY LINK)

Culture & Religion

Malaysia is one of Southeast Asia's most culturally layered countries. Malay, Chinese and Indian influences are all present in the food, architecture, festivals and daily life. It's a big part of what makes the country interesting.

A few things worth knowing before you go:

  • Dress respectfully when visiting mosques or Hindu temples: covered shoulders and knees
  • Remove shoes before entering religious sites
  • Ramadan is observed widely: be mindful of eating and drinking in public during daylight hours if your trip coincides

George Town on Penang island is probably the best single place to experience this cultural mix. The food scene alone is worth the trip.

Wildlife

Borneo is the main event for wildlife in Malaysia, but remarkable encounters are possible across the country. On our trip we saw:

  • Wild orangutans at Semenggoh Wildlife Centre, Kuching
  • Proboscis monkeys in Bako National Park
  • Sea turtles snorkelling in the Perhentian Islands
  • Abundant reef fish and coral throughout the islands

Malaysian Borneo is one of the few places on earth where you can still see wild orangutans at close range. It was one of the most memorable moments of the whole trip.

How Long Do You Need in Malaysia?

3 weeks minimum if you want to combine cities, islands, wildlife and rainforest without feeling rushed. Two weeks is doable but means cutting something real: either Borneo or one of the islands.

If you only have 10–14 days, focus on either the Borneo and KL combination, or the islands and George Town route, rather than trying to squeeze everything in.

Detailed Guides for Each Destination

Here is everything we wrote for each stop:

Frequently Asked Questions About Travelling Malaysia

Is Malaysia safe to travel? Yes. Malaysia is one of the safer destinations in Southeast Asia. Normal city precautions apply in KL, watch your belongings in crowded areas, but we never felt unsafe at any point during the trip.

Do I need a visa for Malaysia? Most European, US, Australian and UK passport holders can enter Malaysia visa-free for up to 90 days. Always check the current requirements for your nationality before travelling.

Can I do Malaysia on a budget? Yes. Street food is exceptional and costs almost nothing, domestic transport is cheap, and budget accommodation is widely available. Travelling comfortably for €50–60/day is very doable.

Is Malaysia good for solo travellers? Yes. English is widely spoken, transport links are good, and the country is easy to navigate independently. The Perhentian Islands in particular have a relaxed, social atmosphere that works well for solo travel.

What vaccinations do I need for Malaysia? Consult your doctor, but commonly recommended are Hepatitis A, Typhoid and routine vaccinations. For Borneo specifically, some travellers also consider a Rabies vaccination depending on planned activities. Check with a travel health clinic before departure.

All recommendations in this guide are based on our own experience. We link directly to the hotels, tours and services we used ourselves.

Marcel Heizelmann
Next

3 Days in Kuala Lumpur: Honest Itinerary, Best Areas & Travel Tips