В 1934 г. правительство выделило Дальстрою четыре самолёта. 29 декабря 1934 г. у причала морского порта Нагаево отшвартовался пароход «Уэлен», на палубе которого стояли укрытые брезентом отечественные самолёты П-5 и С-1. Этим же пароходом прибыл лётный и технический состав. Так началась история магаданской авиации, внёсшей неоценимый вклад в развитие производительных сил Северо-Востока нашей страны. Уже 5 января 1935 г. лётчик Д. Н. Тарасов и штурман М. Д. Меньшиков произвели первую ледовую разведку. С 27 февраля начались первые эпизодические перевозки пассажиров, почты и грузов из Магадана в Балаганное. 25 марта лётчик П. С. Карп совершил первый перелёт через Яблоновый хребет и посадку на р. Колыме в районе Среднекана. 28 марта Д. Н. Тарасов на самолёте П-5 вылетел на выполнение ответственного задания: связаться с «материком» по маршруту Магадан – Хабаровск. Через 13 дней, 9 апреля 1935 г., лётчик благополучно вернулся в Магадан. Путь от Хабаровска до Магадана занял 14 лётных часов.
Авиаторы Дальстроя выполняли самые ответственные задания по доставке необходимых производственных грузов в глубинные пункты Колымы, проведению аэрофотосъемки. В первый год своей деятельности они перевезли 129 пассажиров, налетали 462 часа. Грузоперевозки составили 15 080 тонно-километров. С каждым годом воздушный транспорт приобретал на Северо-Востоке страны всё большее значение для удовлетворения нужд народного хозяйства.
В апреле 1938 г. Всеколымский совет Осоавиахима впервые выпустил лётчиков-учеников, подготовленных в Магадане, которые продолжили обучение в Хабаровской школе пилотов-инструкторов. 24 февраля 1939 г. вылетели из Москвы и взяли курс на Магадан два самолёта Дальстроя. Полёт продолжался 45 лётных часов. Его совершил экипаж в составе пилотов Н. Кузнецова, С. Добрынина, А. Фастрицкого, Н. Шаркова, штурмана М. Меньшикова, бортрадиста П. Кекишева и бортмехаников П. Моторнова и Ф. Родионова. Полёт проходил в труднейших метеорологических условиях. Были совершены посадки в Казани, Свердловске, Красноярске, Иркутске, Якутске и – в 15 часов 45 минут 11 марта – в Магадане. Это был первый полёт магаданцев через всю страну, он положил начало освоению дальневосточных линий.
В начале февраля 1940 г. сдан в эксплуатацию аэродром на 13-м км основной трассы близ Магадана. Большой личный вклад в развитие колымской авиации в тот период внёс командир Магаданского авиапредприятия Ш. И. Шимич.
Значительную роль сыграл воздушный транспорт в развитии производительных сил края в годы Великой Отечественной войны. За четыре года войны авиаторы Дальстроя перевезли 19 680 пассажиров, доставили горнякам, геологам, строителям, рыбакам 5 680 тонн грузов. Общий тоннаж перевозок составил 8 370 тонн. В 1942 г. вступила в строй Особая воздушная трасса АлСиб (Аляска – Чукотка – Колыма – Сибирь – фронт) по перегонке самолётов из США в СССР. Часть трассы проходила по территории Колымы: в п. Сеймчан был построен аэродром для дозаправки и осмотра самолётов, в Гижиге, Магадане и Чайбухе – гидроаэродромы.
В послевоенные годы темпы хозяйственного освоения Северо-Востока возрастали с каждым годом, продолжала развиваться и северная авиация. С целью более эффективной организации лётной работы в марте 1949 г. авиаподразделение было реорганизовано в авиагруппу, в состав которой вошло несколько транспортных авиаподразделений, а в 1952 г. авиагруппа преобразована в Управление воздушного транспорта Дальстроя, которое возглавил Герой Советского Союза В. А. Борисов, в 1968 г. удостоенный звания «Заслуженный пилот СССР». С образованием 3 декабря 1953 г. Магаданской области авиация Дальстроя передана в ведение Главного управления Гражданского воздушного флота и на базе Управления воздушного транспорта создана Магаданская авиагруппа, первоначально вошедшая в состав Дальневосточного управления ГВФ, а с июля 1957 г. подчинённая непосредственно ГУ ГВФ. В начале марта 1954 г. открылось регулярное воздушное сообщение по маршруту Москва – Магадан. На самолёте Ил-12 полёт длился 48 часов. Авиарейсы совершались ежедневно с аэродрома на 13-м километре.
С появлением на линиях Аэрофлота новых турбовинтовых и реактивных самолётов в конце 1950-х гг. было принято решение о строительстве нового аэродрома на 56-м км основной трассы в п. Сокол. 9 августа 1963 г. досрочно закончено строительство первой очереди взлётно-посадочной полосы, и с 10 сентября 1963 г. аэропорт «Магадан» начал регулярно принимать авиалайнеры Ил-18, Ан-10, Ан-12. В 1966 г. строительство аэропорта было завершено в полном объёме. 1 марта 1974 г. в Соколе открылся новый Магаданский аэровокзал, в котором одновременно могли разместиться 400 пассажиров.
В соответствии с приказом Министерства гражданской авиации СССР от 16 июля 1991 г. №167 МОАО-1 был реорганизован с образованием отдельных государственных предприятий: «Аэропорт Магадан», «Авиакомпания “Магаданаэрогруз”», «Авиакомпания “Северо-Восточные грузовые авиалинии”», «Авиакомпания “Полёт”», «Авиакомпания “Колыма Авиа”», «Магаданский центр технического обслуживания “Авиатехника”» и «Авиамедицина».
22 июля 1992 г. открылась регулярная прямая международная пассажирская авиалиния Магадан – Анкоридж (Аляска, США). 23 марта 1994 г. путём объединения компании «Полёт», Магаданского агентства по продаже билетов, наземного комплекса по техническому обслуживанию воздушных судов, медсанчасти, грузовой службы и центра по подготовке и переподготовке авиаперсонала аэропорта «Сокол» создано ФГУП «Авиакомпания “Магаданские авиалинии”».
В 2011 г. аэропорт «Магадан» установил очередной рекорд, обслужив более четверти миллиона пассажиров, в следующем году через аэропорт было перевезено около 9 тысяч тонн почты и грузов. Сегодня воздушные ворота Колымы обеспечивают стабильную связь с Москвой, Благовещенском, Иркутском, Петропавловском-Камчатским, Хабаровском, Новосибирском, а также населёнными пунктами Северо-Восточного региона и Чукотки: Ягодным, Северо-Эвенском, Сеймчаном, Усть-Омчугом, Синегорьем, Омсукчаном, Сусуманом, Омолоном, Кепервеемом. 11 ноября 2008 г. состоялся первый рейс авиакомпании «Якутия» по маршруту Москва – Магадан – Москва на самолёте «Боинг 757-200». В аэропорту «Магадан» после завершения реконструкции взлётно-посадочной полосы впервые приземлился современный авиалайнер такого класса. 6 марта 2013 г. авиакомпания «Якутия» открыла новый рейс по маршруту Магадан – Хабаровск – Магадан на российском самолёте нового поколения SukhoiSuperjet 100. В 2013 г. Магаданская область выразила желание участвовать в проекте «Аэрофлота» по созданию объединённой Дальневосточой авиакомпании.
В декабре 2022 г. в правительстве региона подписали контракт о строительстве нового аэровокзального комплекса, ввод которого по плану должен состояться в декабре 2024 г. Новый терминал Международного аэропорта Магадан будет оснащён двумя телескопическими трапами и автоматической системой обработки багажа, в нём будут реализованы современные технологии обслуживания пассажиров. Архитектурный облик и интерьеры терминала отражают особенности природы, богатство полезными ископаемыми и трудовые достижения Магаданской области. Часть архитектурных решений и интерьеров посвящена Владимиру Высоцкому, чьё имя с 2019 г. носит аэропорт.
Роль воздушного транспорта – одного из основных видов транспорта для Магаданской области оценена по заслугам: в 1979 г. перед зданием аэровокзала в п. Сокол установлен на постамент самолёт Ан-12 с бортовым номером 11355 – один из первопроходцев северных трасс.
