Bandar udara ini dibangun pada Perang Dunia II atas race course wilayah ini (diberitahukan oleh Malta), saat Gibraltar merupakan sebuah markas angkatan laut yang penting untuk Britania. Dibuka pada tahun 1939, bandar udara ini tadinya hanya merupakan lapangan udara darurat untuk Armada Udara Angkatan Laut Kerajaan. Bagaimanapun, setelahnya jalur landasannya dipanjangkan dengan mereklamasi beberapa daratan dari Teluk Gibraltar menggunakan batu yang diledakkan dari Batu Gibraltar sambil melakukan pekerjaan pada terowongan militer. Perpanjangan besar terakhir dari jalur landasan ini memungkinkan kapal udara yang lebih besar untuk mendarat di Gibraltar.

Persengketaan antara Spanyol dan Britania Raya atas wilayah di mana bandar udara ini berdiri (berbeda dengan persengketaan Gibraltar itu sendiri) yang berlanjut telah berdampak serius terhadap pengoperasian bandar udara ini. Pada 2 Desember 1987, sebuah persetujuan ditandatangani oleh pemerintah Britania Raya dan Spanyol untuk memungkinkan bandar udara ini digunakan untuk keperluan sipil.[1] Persetujuan ini mencanangkan pembangunan sebuah terminal baru di kota tetangga milik Spanyol, La Línea de la Concepción berdekatan dengan sisi utara dari batas yang telah ada. Bagaimanapun, persetujuan tersebut dihalangi oleh Pemerintah Gibraltar, dipimpin sejak 1988 oleh Joe Bossano. Akibatnya, persetujuan itu tidak pernah diterapkan.

Sejak itu, Spanyol berhasil mengeluarkan Gibraltar dari inisiatif lebar deregulasi Eropa, mencegah hubungan langsung dari Gibraltar ke negara Uni Eropa lainnya (kecuali Britania Raya), di tempat itu yang tidak memiliki peraturan yang entah bagaimana mengakui kedaulatan Britania Raya atas isthmus may be implemented without a previous agreement on the airport.

Pada penghujung tahun 2005 dan tahun awal 2006, penerapan dari sebuah persetujuan baru merupakan sebuah topik utama dari Forum Trilateral Gibraltar yang diikuti oleh Pemerintah Gibraltar, Spanyol, dan Britania Raya. Hasilnya, Persetujuan Córdoba ditandatangani pada 18 September 2006 oleh seluruh pihak. Hal ini menyelesaikan semua pelarangan diskriminatif pada penerbangan sipil ke Bandar Udara Gibraltar, termasuk pelarangan penerbangan di atas tanah Spanyol, dan penghindaran Gibraltar dari semua persetujuan Uni Eropa di angkutan udara, memungkinkan penerbangan sipil dari semua negara ke Bandar Udara Gibraltar Airport.[2]

Pada 17 November 2006, Iberia Airlines mengumumkan bahwa mereka akan memulai penerbangan dari Madrid ke Gibraltar menggunakan pesawat Airbus A319. Hal ini merupakan pergerakan penting karena tidak ada maskapai Spanyol yang pernah terbang ke Gibraltar sejak 1979, karena status persengketaannya. Iberia memulai penerbangan ke Bandar Udara Gibraltar pada 16 Desember 2006 dengan sebuah penerbangan dari Madrid yang mengikutsertakan beberapa pejabat Pemerintah Spanyol.

Pada 12 September 2008, Monarch kembali melayani penerbangan dari Gibraltar ke Bandar Udara Manchester. Monarch menghentikan rutenya tersebut pada 19 Juli 2006 karena alasan biaya, namun telah memutuskan untuk mengembalikannya. Rute tersebut akan beroperasi 3 kali seminggu setiap hari Senin, Rabu, dan Jumat (tidak 4 kali seminggu seperti yang lama sebelum ia dihentikan). Rute tersebut juga beroperasi pada hari Kamis dan Ahad di musim panas.

Pada 22 September 2008, Iberia mengumumkan bahwa mereka akan menghentikan penerbangannya ke Madrid mulai 28 September karena "alasan ekonomi", yaitu, sepinya permintaan. Hal ini membuat Gibraltar, sekali lagi, tidak memiliki hubungan udara dengan Spanyol.[3]

Pada April 2009, Ándalus Líneas Aéreas mengembalikan hubungan udara Gibraltar dengan ibu kota Spanyol.[4] Pada Juli 2009, Ándalus juga memulai jadwal penerbangan ke Barcelona, menambahkan tujuan di Spanyol menjadi 2.[5] Bagaimanapun, maskapai tersebut menghentikan pelayanannya di rute ini pada September 2009 karena sepinya permintaan.[6] Pada April 2010, telah dikonfirmasi bahwa penerbangan Ándalus ke dan dari Gibraltar telah ditutup secara permanen.[7] Dan sekali lagi, Gibraltar tidak memiliki hubungan udara ke Spanyol. Ándalus Líneas Aéreas berhenti beroperasi pada 13 Agustus 2010.

Pada Desember 2010, EasyJet mengumumkan bahwa sebuah rute baru yakni Gibraltar ke Liverpool. Hal ini merupakan kali pertama di mana sebuah maskapai mengoperasikan sebua penerbangan dari Liverpool ke Gibraltar. Rute tersebut akan beroperasi pada hari Selasa, Kamis, dan Sabtu, kemungkinan untuk mengurangi penundaan di banda udara dan bentrok dengan penerbangan Monarch ke Manchester.

Pada 18 Mei 2011, Bmibaby mengumumkan bahwa mereka akan melaksanakan penerbangan dari Gibraltar ke East Midlands mulai 31 Maret 2012. Hal ini merupakan kali pertama sebuah maskapai mengoperasikan sebuah penerbangan dari East Midlands ke Gibraltar. Rute ini akan beroperasi pada hari Selasa, Kamis, dan Sabtu dan akan dioperasikan dengan Boeing 737-300.