Pada awalnya, lapangan terbang Tawau terletak di Jalan Utara yang terletak dua batu dari Tawau. Lapangan terbang tersebut dibuka secara rasminya pada tahun 1968 oleh bekas Menteri Pengangkutan Malaysia, Tan Sri Haji Sardon. Ia hanya digunakan untuk menampung pesawat kecil contohnya Fokker 50.

Pada awal 80-an, Boeing 737 milik syarikat Penerbangan Malaysia (MAS) membuat penerbangan sulung ke lapangan terbang Tawau selepas landasannya diperbesarkan. Semenjak itu, lapangan terbang tersebut telah menerima penerbangan dari Kota Kinabalu, Sandakan dan Lahad Datu.

Walau bagaimanapun, pada 15 September 1995, sebuah pesawat Fokker 50 milik MAS yang membuat penerbangan dari Kota Kinabalu mendarat 500m dari hujung landasan 2200m tersebut. Dalam cubaan untuk membuat pusingan, pesawat tersebut teerhempas ke sebuah perkampungan Melayu, kampung Seri Menanti, mengakibatkan 34 kematian termasuk dua krew pesawat.

Lebih awal lagi, pada 20 Mac 1995, sebuah pesawat kargo Cessna Caravan turut terhempas ke perumahan berikutan gagal untuk berlepas. Sebuah lagi pesawat Boeing 737 telah tergelincir dari landasan pada Oktober 2001 tanpa menyebabkan sebarang kecederaan kepada penumpang.

Mengikut satu tinjauan, lapangan terbang lama mempunyai landasan yang terpendek di Malaysia. Tidak lama kemudian, sebuah lapangan terbang antarabangsa baru berada dalam rancangan kerajaan untuk memindahkan lapangan terbang Tawau ke lokasi baru sekitar lebuh raya Tawau - Semporna, 30km dari Tawau.

Lapangan terbang tersebut kemudiannya dibuka untuk umum pada Disember 2001. Pada tahun 2003, Lapangan Terbang Tawau dilancarkan secara rasmi oleh bekas Menteri Pengangkutan Malaysia, Tun Dr. Ling Liong Sik. Lapangan Terbang Tawau menjadi lapangan terbang kedua terbesar di Sabah selepas Lapangan Terbang Antarabangsa Kota Kinabalu.