1958年,那霸與鄰近島嶼的機場,包括宮古島以及石垣島,在美軍接管日本下於沖繩縣成立琉球航空。於1967年6月20日,琉球航空由日本航空出資成立當時稱為日本南西航空(英語:Southwest Air Lines),並於同年7月開始營運,直至1993年7月才改成現時日本越洋航空的名稱。初期日本越洋航空以康維爾240營運,直到母公司日本航空提供資金,允許其升級為YS-11,最後波音737。當日航飛機設備發生故障時,日本越洋航空會出借飛機予日航。日本越洋航空亦為日航集團旗下的波音737-400提供維修。日本越洋航空擁有琉球空中通勤69.8%的股權。