L'aeroport es va construir l'any 1933 com a Aeròdrom d'Oroku (小禄飛行場) per part de la Marina Imperial Japonesa. El 1945, després de la Segona Guerra Mundial, van passar a usar-lo les Forces Aèries dels EUA amb el nom d'Aeròdrom de Naha (那覇飛行場). L'any 1972 va acabar l'administració d'Okinawa per part dels EUA que va retornar al Japó, però l'aeroport va romandre com a base militar estatunidenca fins a l'any 1982, en què es va transferir a la Força Aèria d'Autodefensa del Japó.