Авиакомпания Trans-Pacific Airlines была основана 26 июля 1946 года бизнесменом Руди Тонггом в качестве чартерного перевозчика и главного конкурента другой компании Hawaiian Airlines[2]. Первые рейсы выполнялись между городами Гонолулу, Мауи и Хило на единственном самолёте Douglas C-47 (DC-3) времён Второй мировой войны. Первоначальное название авиакомпании свидетельствует об амбициозных планах её основателя по покрытию маршрутной сетью перевозок всего тихоокеанского региона, включая Гавайские острова, Калифорнию и Китай. К концу 1946 года авиакомпания получила неофициальное прозвище «The Aloha Airlines» («Любимая авиакомпания») и имела к тому времени в своём флоте четыре самолёта. 21 февраля 1949 года Президент США Гарри Трумэн подписал официальное разрешение на открытие Trans-Pacific Airlines регулярных авиарейсов, первый регулярный пассажирский рейс был выполнен 6 июня 1949 года между аэропортами Гонолулу и Хило.

В 1952 году авиакомпания впервые достигла прибыли, составшившей по итогам финансового года показателя в 36 410,12 долларов США. При этом стоимость акций компании на фондовой бирже выросла за отчётный год на 30 %, в сравнении с 10 % роста в 1950 году. В 1952 году авиакомпания изменила своё официальное название на TPA-The Aloha Airline. Тем не менее, в последующие пять лет дальнейший рост финансовых показателей авиакомпании практически остановился по причине того, что её главный конкурент Hawaiian Airlines ввела в эксплуатацию современные самолёты Convair 340 и фактически перехватила подавляющую часть рынка авиаперевозок в регионе. В 1958 году на пост президента авиакомпании был избран бизнесмен, специализировавшийся на сделках с недвижимостью, Хунг Во-Цзин (Hung Wo Ching), чья семья к тому времени владела значительной долей акций перевозчика. В ноябре того же года компания очередной и последний раз сменила своё название на Aloha Airlines, а 15 апреля 1959 года воздушный флот авиакомпании пополнился современными турбовинтовыми лайнерами Fairchild F-27 с усиленным килем и более толстой обшивкой фюзеляжа по сравнению с другими самолётами той же серии (руководство компании высказывало некоторые опасения насчёт безопасности эксплуатации лайнеров-высокопланов на взлётно-посадочных полосах аэропортов с грунтовым покрытием). Летом 1959 года доля перевозок Aloha Airlines на региональном рынке взлётела до 42 процентов.