Магаданский горисполком 28 ноября 1958 года принял решение об отводе земельного участка Магаданской отдельной авиагруппе гражданского воздушного флота под строительство аэродрома в районе 56 км автотрассы. Уже в августе 1963 года было окончено строительство первой очереди взлетно-посадочной полосы новой воздушной гавани территории, и с 10 сентября 1963-го аэропорт начал регулярно принимать авиалайнеры Ил-18, Ан-10, Ан-12. В 1966 году строительство аэропорта было завершено в полном объеме. 1 марта 1974 года в поселке Сокол открылся новый магаданский аэровокзал, в котором одновременно могли разместиться 400 пассажиров, сообщает ИА MagadanMedia.

В начале 1963-го года руководством ГУ ГВФ было принято решение о перебазировании материальной части и личного состава 185-го объединенного авиаотряда из аэропортов "13-й" и "47-й км" в аэропорт "Магадан-56 км".

Как писал историк и краевед Давид Райзман, в то время "ни сам аэродром, ни службы нового аэропорта в современном понимании "готовность аэропорта" не были готовы к приему ВС и обслуживанию пассажиров".

В приказе начальника ГУ ГВФ при Совете Министров СССР от 4.05.1963 № 318 "Об открытии регулярных полетов самолетов Ан-10, Ан-12 на строящемся аэродроме "Магадан-56" говорилось: "...Учитывая крайнюю необходимость Магаданской области и Северо-Восточного совнархоза в перевозке большого количества пассажиров и грузов, а также отсутствие другого вида транспорта и невозможность выполнить объем перевозок поршневой авиацией, на основании акта комиссии технического рейса, выполненного на самолете Ан-10 специалистами ГУГВФ, ДВТУ, МОАГ ГВФ, приказываю: 1. Разрешить в весеннее-летний период 1963 года в виде исключения полеты на самолетах Ан-10, Ан-12 на подготовленную часть ВПП размером 1630х60 метров строящегося аэродрома "Магадан-56" со следующими ограничениями..."

К полетам на аэродром "Магадан-56" допускать наиболее опытные экипажи, предварительно привезенные на данный аэродром с техническими посадками с обоих направлений...

Первые полеты на обычном транспортном самолете Ил-14 выполняли в Охотском море пилоты Н.Ф. Прокопенко, впоследствии командир авиаподразделения, заслуженный пилот СССР, П.М. Семка, штурман Н.А. Назаров и бортрадист Болдырев. В январе 1965 года на аэродроме "Магадан-56" принимали первые лайнеры Ан-12.

С 1955 по 1968 годы аэродромы Магадана-13 км, 47 км и 56 км вместе с аэродромами районов области позволили увеличить авиаперевозки пассажиров - в 5,4 раза, почты - в 12,3 раза, грузов - в 31 раз. Санитарная авиация в 1968 году бесплатно выполнила почти 1,5 тысячи вызовов, перевезла более 6,5 тысячи больных и врачей и 128 тонн медицинского груза.

В 1973 году в поселке Сокол состоялось открытие нового здания аэровокзала. 400 авиапассажиров одновременно могли получить профессиональные и комфортные услуги "Аэрофлота".

Статус международного аэропорта "Магадан-56 км (Сокол)" приобрел 2 июня 1991 года....