В компанию вошли две эскадрильи тяжелых поршневых самолетов, эскадрилья легких лайнеров и аэропорт "Магадан-56" 2 класса

Приказом Главного управления ГВФ 18 июля 1963 года организован Магаданский объединенный авиаотряд, включивший в себя 185-й летный отряд 3-го класса, состоявший из двух эскадрилий тяжелых поршневых самолетов и одной эскадрильи легких самолетов и вертолетов (Ан-2, Ми-1, Ми-4), и аэропорт "Магадан-56" 2-го класса. Командиром авиаотряда назначен Иван Кучерявый. В это же время самолеты Ли-2 были переданы в Певек в отдельную эскадрилью, сообщает ИА MagadanMedia.

В 1964 году в составе Магаданского объединенного авиаотряда был организован 258-й летный отряд, состоящий из двух эскадрилий самолетов и вертолетов с базированием в аэропорту 13 км.

В 1970-е годы в состав МОАО были включены 181-й летный отряд, приписные аэродромы "Чайбуха" (бывший "Гижига"), "Сусуман" (бывший "Берелех") и "Синегорье".

К началу 1990-х годов в международном аэропорту Магадан принимали большинство отечественных самолетов, включая Ту-204-100, Ан-72, Ан-74, а также Боинг-727.

Перестроечные годы, переход экономики на рыночные отношения повлекли за собой структурные изменения. В соответствии с приказом Министерства гражданской авиации СССР № 167 от 16 июля 1991 года, Магаданский объединенный отряд был реорганизован с образованием отдельных государственных предприятий:

ГП "Аэропорт Магадан", ГП "Авиакомпания "Магаданаэрогруз", ГП "Авиакомпания "Северо-Восточные грузовые авиалинии", ГП "Авиакомпания "Полет", ГП "Авиакомпания "Колыма Авиа", ГП "Магаданский центр технического обслуживания "Авиатехника" и "Авиамедицина".

Приказом Магаданского управления гражданской авиации от 21 августа 1991 года № 173 в соответствии с приказом МГА от 16 июля 1991 года правопреемником стал аэропорт Магадан....