Usai Timor Timur (sekarang bernama Timor Leste) resmi lepas dari NKRI pada 19 Oktober 1999, negara tersebut masih mengandalkan maskapai asal Indonesia, seperti Garuda Indonesia dan Merpati Airlines, untuk tetap menghubungkan negaranya dengan dunia luar.
Baca juga: Usai 56 Tahun, BN2 Islander Tetap Diproduksi! Pernah Ikut Operasi Seroja di Timor-Timur
Ketika itu, Timor Leste belum mempunyai maskapai penerbangan sendiri. Kapanpun maskapai dari Indonesia dan negara lainnya memutuskan stop operasi, sudah pasti mereka terisolir. Namun, itu tak akan terjadi pasca lahirnya Air Timor.
Dihimpun dari berbagai sumber, Air Timor resmi berdiri pada tahun 2010. Sebelum itu, maskapai tersebut beroperasi dengan brand Austasia Airline, mengoperasikan penerbangan charter berjadwal antara Australia dan Indonesia dari tahun 2001 sampai 2007.
Di tahun 2007, maskapai itu berkantor di Dili, Timor Leste dan terdaftar sebagai Air Operator Certificate (AOC) di sini selain juga terdaftar AOC di Singapura.
Setelah mendapat persetujuan dari Pemerintah Timor Leste, Austasia Airlines memulai penerbangan charter berjadwal pertamanya dari Singapura ke Dili pada Agustus 2008 dengan melayani penerbangan seminggu dua kali pada hari Selasa dan Sabtu dengan pesawat Airbus A319 wet lease dari Silk Air.
Setelah lama beroperasi di Timor Lester, barulah pada tahun 2010, Austasia Airlines mengajukan permohonan untuk menjadi perusahaan nasional (bukan maskapai penerbangan nasional karena sampai detik ini Timor Leste belum mempunyainya) dan mengubah namanya menjadi Air Timor SA. Ini pun disetujui Pemerintah Timor Leste.
Usai menjadi maskapai nasional Timor Leste, Air Timor makin menggeliat. Di tahun 2015, Air Timor sempat melontarkan niatnya turut meramaikan pasar penerbangan perintis di Timur Indonesia, mulai dari Kupang sampai Makassar.
Hanya saja, di tahun yang sama Air Timor mengaku mulai kesulitan lantaran kebijakan pemerintah memberikan izin terbang dari dan ke Dili kepada maskapai asing.
Sebelumnya, Air Timor memang aktif menghubungkan Timor Leste dengan Indonesia, Singapura, dan Australia. Armadanya sendiri didapat dengan cara menyewa ke maskapai di tiga negara itu. Untuk rute Dili-Denpasar, Air Timor mempercayakannya pada Citilink, baik terbang langsung antar dua kota itu ataupun menyewa pesawat darinya.
Baca juga: MyTimor, Aplikasi Ride Hailing Besutan Telkomcel untuk Masyarakat Timor Leste
Begitu juga dengan rute Dili-Singapura dan Dili-Darwin, Air Timor mengoperasikannya berkat dukungan airlines lokal; Silk Air dan Airnorth.
Di akhir tahun 2015, Sriwijaya Air dan anak perusahannya, Nam Air, diizinkan menerbangi rute Dili-Denpasar berjadwal. Sejak kehadiran maskapai tersebut, bisnis Air Timor kacau dan di tahun 2017 maskapai mengaku dalam kondisi sulit. Bahkan, maskapai membukukan kerugian mencapai US$4 juta.
 resmi lepas dari NKRI pada 19 Oktober 1999, negara tersebut masih mengandalkan maskapai asal Indonesia,){kind=link}