Syarikat penerbangan itu ditubuhkan pada 23 April 1996 sebagai sebuah Syarikat Sendirian Berhad oleh Surendra Bahadur Basnet, pesara hakim Mahkamah Agung dan mantan menteri kerajaan; dan anaknya Birendra Bahadur Basnet.[7][8] Operasi bermula pada 11 Oktober 1997 dengan penerbangan bersiar-siar ke Gunung Everest menggunakan Beechcraft 1900D baru.[9] Dalam tempoh sepuluh tahun, syarikat ini telah berkembang menjadi sekumpulan tujuh 1900D[10]. Pada tahun 2008, pinjaman daripada International Finance Corporation membenarkan syarikat ini memperluaskan lagi dengan membeli dua pesawat ATR 42.[11] Buddha Air mengambil penghantaran 70 tempat duduk pertama ATR 72-212 pada bulan Jun 2010. Nama syarikat penerbangan itu berasal dari perkataan Sanskrit 'Buddha', sebuah gelaran yang digunakan untuk Siddharta Gautama yang sangat dihormati.