Pada 17 Mei 2007, Tony Fernandes mengumumkan rancangan untuk memulakan penerbangan dari Malaysia ke Australia. Fernandes telah berkata dia akan mengelak Lapangan Terbang Antarabangsa Sydney disebabkan oleh yuran yang tingginya, sebaliknya menumpukan perhatian ke atas lapangan terbang alternatif yang lebih murah seperti Lapangan Terbang Avalon berdekatan Melbourne, Newcastle dan Adelaide.

Laluan AirAsia X pertama adalah Kuala Lumpur ke Gold Coast, Australia. Tambang sehala bagi laluan ini bermula pada MYR 60 (AUD 31) tanpa cukai dan caj tambahan, dengan tambang dua hala adalah kira-kira MYR 1,900 (AUD 647) tanpa cukai tambahan.[2]

Syarikat penerbangan juga mengumumkan Sir Richard Branson dari Virgin Group akan mengambil syer sebangak 20% ke dalam AirAsia X untuk membantu operasi permulaan seperti membiayai pembelian pesawat-pesawatnya.[3][4] Branson juga meramalkan kemungkinan mengadakan hubungan rapat di antara Virgin Blue dan AirAsia X, seperti perkongsian kod dan program frequent flyer pada masa kelak.[5][6]

Pesawat pertama AirAsia X, tiba di Lapangan Terbang Antarabangsa Kuala Lumpur, Malaysia pada 15 September 2007. Ia dinamakan "Semangat Sir Freddie" untuk memperingati perintis dan pengasas penerbangan kos rendah Sir Freddie Laker, Skytrain di Eropah.[7]

FlyAsianXpress

FlyAsianXpress (FAX) pernah menjadi penerbangan ketiga terbesar di Malaysia yang membuat operasi luar bandar di Sabah dan Sarawak. Penerbangan sulungnya adalah pada 1 Ogos 2006 walaupun terpaksa ditunda selama 50 minit akibat cuaca buruk.[8] FAX menegaskan bahawa mereka bukan memegang konsep penerbangan tambang rendah (LCC)[9] tetapi mengadaptasikan amalan-amalan AirAsia untuk mengurangkan kos, iaitu seperti tempahan internet dan telefon, serta sistem tidak bertiket. Walau bagaimanapun, semua operasi FAX ditamatkan selepas pengambilalihan semula laluan luar bandar oleh Penerbangan Malaysia, melalui MASwings. Oleh itu, FAX akan memfokuskan operasinya kepada AirAsia X.

FlyAsianXpress dan AirAsia X

Dengan penamatan operasi luar bandar oleh FAX, nama korporat telah ditukar menjadi AirAsia X Sdn. Bhd.