28 ноября 1958 года Магаданский горисполком принял решение "Об отводе земельного участка Магаданской отдельной авиагруппе гражданского воздушного флота под строительство аэродрома в районе 56 километра автотрассы", ныне этот аэропорт известен как Сокол.

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

Со 2 июня 1991 года аэропорт "Магадан-56 км" или Сокол имеет статус международного. А ныне 300 специалистов мирового уровня возводят для него новый терминал, полностью соответствующий этому статусу.