Durante sus primeros días, el aeropuerto de Tawau estaba situado en Jalan Utara, literalmente, conocida como la carretera del norte, alrededor de 3,2 km de distancia a Tawau. El aeropuerto fue inaugurado en 1968 por el exministro de Transporte de Malasia, Tun Sardon Haji Jubir. Solo se utilizaba para abastecer a las aeronaves pequeñas, como las Fokker 50. A principios de los años 80, el aeropuerto recibió su primer vuelo Boeing 737 operado por Malaysia Airlines, al tener una nueva pista extendida. El aeropuerto también pasó a ser destino regional por parte de las ciudades de Tarakan, Balikpapan y Makassar en Indonesia gracias a Bouraq Indonesian Airlines y Merpati Nusantara Airlines durante ese período, debido a la proximidad geográfica y los estrechos vínculos socioeconómicos entre Tawau y las principales zonas urbanas del este de Indonesia. El 15 de septiembre de 1995, el vuelo 2133 de Malaysia Airlines, un vuelo de Kota Kinabalu operado por un avión Fokker 50, aterrizó 500 m antes del final de la pista de 2200 m de largo. Mientras intentaba dar un rodeo, el avión se estrelló contra una villa llamada Kampung Seri Menanti.​ Hubo 34 muertes, incluidos dos miembros de la tripulación.​ En octubre de 2001, otro vuelo de Malaysia Airlines (este operado por un Boeing 737-400) se salió de la pista sin causar heridos ni víctimas mortales. Una encuesta encontró que el antiguo aeropuerto de Tawau tenía una de las pistas más cortas de Malasia. La pista del aeropuerto debería…