Bandar Udara Internasional Ngurah Rai Bandar Udara Ngurah Rai dibangun tahun 1930 oleh Departement Voor Verkeer en Waterstaats (semacam Departemen Pekerjaan Umum). Landas pacu berupa "airstrip" sepanjang 700 m dari rumput di tengah ladang dan pekuburan di desa Tuban. Karena lokasinya berada di Desa Tuban, masyarakat sekitar menamakan "airstrip" ini sebagai Pelabuhan udara Tuban. Tahun 1935 sudah dilengkapi dengan peralatan telegraph dan KNILM (Koninklijke Nederlands Indische Luchtvaar Maatschappij) atau Royal Netherlands Indies Airways mendarat secara rutin di "South Bali" (Bali Selatan), yang merupakan nama lain dari Pelabuhan Udara Tuban.
Tahun 1942 South Bali Airstrip dibom oleh Tentara Jepang, yang kemudian dikuasai untuk tempat mendaratkan pesawat tempur dan pesawat angkut mereka. Airstrip yang rusak akibat pengeboman diperbaiki oleh Tentara Jepang dengan menggunakan "Pear Still Plate" (sistem plat baja).
Lima tahun berikutnya 1942-1947, "airstrip" mengalami perubahan. Panjang landas pacu menjadi 1,2 km dari semula 700 m. Tahun 1949 dibangun gedung terminal dan menara pengawas penerbangan sederhana yang terbuat dari kayu. Komunikasi penerbangan menggunakan "transceiver" kode morse.
Untuk meningkatkan kepariwisataan Bali, Pemerintah Indonesia kembali membangun gedung terminal internasional dan perpanjangan landas pacu kearah barat yang semula 1,2 km menjadi 2,7 km dengan "overrun" 2×100 meter. Proyek yang berlangsung tahun 1963-1969 diberi nama Proyek Airport Tuban dan sekaligus sebagai persiapan internasionalisasi Pelabuhan Udara Tuban.
Proses reklamasi pantai sejauh 1,5 km dilakukan dengan mengambil material batu kapur yang berasal dari Ungasan dan batu kali serta pasir dari Sungai Antosari – Tabanan.
Seiring selesainya "temporary terminal" dan "runway" pada Proyek Airport Tuban, pemerintah meresmikan pelayanan penerbangan internasional di Pelabuhan Udara Tuban, tanggal 10 Agustus 1966.
Penyelesaian Pengembangan Pelabuhan Udara Tuban ditandai dengan peresmian oleh Presiden Soeharto pada tanggal 1 Agustus 1969, yang sekaligus menjadi momen perubahan nama dari Pelabuhan Udara Tuban menjadi Pelabuhan Udara Internasional Ngurah Rai ("Bali International Airport Ngurah Rai").
Untuk mengantisipasi lonjakan penumpang dan kargo, maka pada tahun 1975-1978 Pemerintah Indonesia kembali membangun fasilitas-fasilitas penerbangan, antara lain dengan membangun terminal internasional baru. Gedung terminal lama selanjutnya dialihfungsikan menjadi terminal domestik, sedangkan terminal domestik yang lama digunakan sebagai gedung kargo, usaha jasa katering, dan gedung serba guna.
Proyek FBUKP tahap I (1990 – 1992) meliputi Perluasan Terminal yang dilengkapi dengan garbarata ("aviobridge)", perpanjangan landas pacu menjadi 3 km, relokasi "taxiway", perluasan "apron", renovasi dan perluasan gedung terminal, perluasan pelataran parkir kendaraan, pengembangan gedung kargo, gedung operasi serta pengembangan fasilitas navigasi udara dan fasilitas catu bahan bakar pesawat udara.
Proyek FBUKP tahap II (1998-2000), pengembangan bandara dikerjakan oleh Direktorat Jenderal Perhubungan Udara, antara lain dengan memanfaatkan hutan bakau seluas 12 ha untuk digunakan sebagai fasilitas keselamatan penerbangan.
Rencana Proyek FBUKP tahap III meliputi Pengembangan Gedung Terminal, Gedung Parkir, dan Apron. Luas terminal domestik saat ini hanya akan dikembangkan hingga total luasnya mencapai 12.000 m² yang nantinya akan digunakan sebagai terminal internasional. Adapun eksisting terminal internasional akan dialihfungsikan menjadi terminal domestik. Dengan kondisi tersebut, Bandara Ngurah Rai akan mampu menampung hingga 25 juta penumpang.
Bandara ini memiliki satu terminal domestik dan satu terminal internasional.
Saat ini, terminal domestik menempati area terminal internasional lama. Terminal domestik keberangkatan memiliki 8 gerbang, gerbang 1A, 1B, 1C, 2, 3, 4, 5, dan 6. Terminal domestik kedatangan memiliki 4 pengambilan bagasi.