Sandakan Restaurants

Fantastic dessert especially their frozen yogurt & home baked cheesecakes. Great ambient n reasonable price.
You can't believe a great dessert place hiding here.

Favorite Dish: Delicious low fat frozen yogurt and even their ice cream less sweet n great variety.

The Restaurant looks big and grand but suprisingly the price is cheap and the food is really fresh. They serve chinese food & steamboat. You will be able to catch it by the road side when you pass by mile 4. Check it out and i can ensure you that you will not regret :) Their service is marvellous and each waitor/waitress will look after each table.

Steamboat costs around RM12 per person & price of dishes starts from RM10 onwards...
I paid USD100 for seafoods & higher range dishes for 10 people.

Favorite Dish: Fresh Steam Fish ("Sek Ban" in cantonese)
Fried Crystal Prawn with Salad Sauce
Chinese Style Beef Steak
Golden Coin Chinese Tofu
Fried Pig Skin ("Yue Zhu" in cantonese)
Sweet & Sour Crab
Shark Fin Soup with sliced Chicken meat

This became one of the best places I ate at during my time in Malaysia. Now, I don't like tomatoes! Hate the mere mention of them, in fact, so to come to a restaurant named after them made my skin crawl a little but I knew at the back of my mind to not expect to see them on the menu. And I was right and so calmed down! To say that the menu is comprehensive and extensive is an understatement. There's just page after page of it with a huge range of dishes (RM5-6) with some eye-catching sauces such as HP sauce, marmite and Sprite Chicken! Oh, and the fruit juices are great as well.

There are not many chocolate makers in Malaysia, let alone when you are as far out as Sandakan. Everything we were told said that this is the one and only in town.

The prices are quite reasonable and the quality is quite nice. There were about a dozen flavors to choose from, including white, milk and dark chocolates. They had various fruit mixes and nuts as well.

Favorite Dish: The only thing the shop sells are chocolates.
Be prepared to eat them quickly unless you have a way to keep them from melting outside!

There are several restaurants along the waterfront Esplanade. Prices may vary, but in my opinion, the Harbor Bistro Cafe has the highest consistency of quality for the price. The venue is almost always busy for dinner, but you should never have to wait but a couple minutes to be seated. If you come early, you can get a table closer to the water, but all tables are outdoor on the Esplanade walkway.

Favorite Dish: All the food is good, but I was particular to the fish dishes. The sweet onion grilled fish was wonderful, as were the noodles and other dishes.

1 more image

After having a look through the Central Market with our guide, he took us to the area where all the eateries are located. There are plenty, and the choice is big. He wanted me to try "fish head soup" something I couldn't bring myself to do.
I had a look at the prices, and the meals were very cheap, maybe a place to remember for that cheap meal when in Sandakan.

In Sandakan go to the Ocean King Seafood Restaurant at Sandy Plan 4km from the town. Serve mostly all type of seafoods. Restaurant is built on stilts on the sea. Very breezing in the evening. Prices are average, cheaper than KL. Taxi will take you there, but ask for pickup after dinner.

For deserts, try SevenHeaven or Equator in Bandar Indah at ml. 4. There are also few open air pubs at Bandar Indah too.

You can choose the fresh/live seafood by yourself! This restaurant located 3km away from town, so you have to take a taxi to go and back. Check the price with the cabbie b4 going.
we(2pax) spend around RM72 for 5 dishes( mantis prawn, oyster, fry sotong, clams and vegi).