Historia Cairns Airport sięga 1928 roku, kiedy Tom McDonald zaczął latać swoim De Havilland DH.60 Moth na piasku w pobliżu obecnego lotniska. Mógł lądować tylko na ziemi i między przypływami. Podczas jednego awaryjnego lotu, McDonald został zmuszony do startu z beczki z piwem.
Podczas II wojny światowej rząd australijski kupił lotnisko do użytku przez Royal Australian Air Force. W 1943 roku główny pas startowy uzyskał twardą nawierzchnię i został wydłużony do obsługi samolotów wojskowych. Był również wykorzystywany przez United States Army Air Forces jako baza transportowa dla 33 Squadron Troop Carrier (374 Troop Carrier Group) w 1942 roku. W 1949 roku główny pas startowy został wydłużony do 1730 metrów, aby pomieścić większe samoloty. W połowie lat 60. XX wieku lotnisko zostało zmodernizowane i dalej wydłużony pas startowy do 2020 metrów i wzmocniony, tak by mogły lądować samoloty odrzutowe.