Tarakan  is the capital of North Kalimantan on an island of the same name formerly a town in East Kalimantan. 100km south of Nunukan, it also serves as a visa-free border-crossing between Indonesia and the Malaysia town of Tawau in Sabah.
To/from Tawau: One departure daily except on Sunday from Tawau. M.V. Indomaya sails every Monday, Wednesday and Friday at 11.30am, while M.V. TawindoM.V Labuan Express departs every Tuesday, Thursday and Saturday at 10.30am. Tickets cost RM130 to RM140 (depending on which ferry you get on) one-way and travelling time is 4 hours (and thats not counting the usual 1 hour delay in departure time).
Be prepared to pay porters to haul your bags for you. On the Malaysian side, RM10 should be sufficient, on the Indonesian side about 20,000-30,000 rupiah for a couple suitcases. In Tawau, the ferry docks at the Customs jetty behind the fish market. In Tawau, the ferry docks at Tengkayu port, which is close to the city center. The jetty, in this case, is a very long walk to the customs/immigration building. The minute the ferry docks (at either port), a crowd of porters will jump on board and hustle to grab your bags.
Alternative travel : A less mind numbing way of travel to Tarakan is to take the ferry service which plies a few times a day between Nunukan and Tawau, and a twice daily flight that goes between Nunukan and Tarakan. To get into Tawau this way, take the 11AM ferry (which usually waits to depart until it's full, which can mean it leaves at noon) from Tawau to Nunukan. The Labuan Express is the best option because it is just plain cleaner than the other ferries. The journey will take 45 minutes to an hour and it costs 40 Ringgit. After getting through Indonesian immigration, catch a minibus (RP 20,000 to charter the whole thing, and be prepared to bargain) to the airport which is a mere 15 minutes drive. There's a Kalstar plane (French ATR propellor plane which can seat 50 people) that arrives at 1:30pm to 2:00pm and you can catch that to Tarakan. Its RP 250,000 for that ticket which you can purchase at the airport. Oh, and there's some other tax of RP 8,000 too. The journey takes less than 15 minutes.
Of course you can travel to Tarakan from the Indonesian side (mainly going through the oil city of Balikpapan). From Balikpapan there are three to four flights daily except Sundays. By the way, if you do choose to go through Balikpapan airport, try the "Nasi Sop Buntut" at the Blue Sky restaurant on the second floor of the airport. Right beside the viewing gallery. Excellent stuff. Probably the best in Kalimantan ...
Blue mini van take you around for 3,000. Though they can change up to 20,000 to go to the airport.
SWISS-BELHOTEL - the hotel of choice for most business travelers. Expect to pay from between 450,000 Rp to 750,000 Rp net per night. Clean and centrally located.
Tarakan Plaza Hotel - newly renovated and just re-opened for business. This is one of the oldest hotels in Tarakan and it used to be the best. But that was 10 years ago. Today it's been redone from the outside in. Unfortunately it still can't shake the "old & dark" feeling that old and dark hotels have. Room rates are from 280,000 RP per night.
Bahtera Hotel - another oldie but this hotel has a little bit more character. Another member of the old and dark hotel club, but its saving grace is its gardens and low density lay out. It also has an infamous massage parlour, an ear-drum wrecking dance hall, and dingy karaoke rooms complete with hostess viewing "aquariums".
Samkho Hotel - somewhat old and dingy, but reasonable in price (270,000 Rp or so).
Grand Taufiq Hotel provides three types of Room with different features. There are 45 rooms incuding 3 Executive rooms, 12 Deluxe rooms and 30 standard rooms which completed with lift, minibar, coffee shop, meeting room and also television channels. Below is the room's rate that Grand Taufiq Hotel offer. Grand Taufiq Hotel located in the middle of Tarakan, it takes few minutes to reach the harbor, airport and center of trading. Therefore, you may continue your journey easily to Nunukan, Bulungan, Malinau, Berau, Derawan island and also Tawau (border between Indonesia and Malaysia).contact Suri(manager): +6285350296824
If you are flying don't forget the 30,000 for airport tax that has to be paid at the airport before boarding. It's not included in the ticket regardless of what the travel agent may tell you.