The airport was inaugurated on 12 January 1961. It was then called Magadan-56 (due to its location on the 56 km on the Kolyma highway) and took over all passenger air services in the region. Only special-purpose flights were operated from the old airport (Magadan-47; (Russian: Магадан-47/3 (Северный)) which was located at 59°54′50″N 150°53′07″E. In subsequent years, the value of the Magadan-47 airfield was lost, because the unpaved runway did not meet the new technical requirements.

In 1978, Promstroy began to reconstruct the runway and ground services buildings. On 13 December 1980, the first Il-62 aircraft landed at Magadan Airport. From the next day, airliners began to make regular non-stop flights from Magadan to Moscow.

On 20 May 1979, at the forecourt square in the Magadan airport, the unveiling of a monument of labor glory took place: the An-12 aircraft with tail number USSR-11355. For almost 13 years, the airliner worked in the Magadan squadron, performing transportation in the Far North-East. The Magadan Squadron, formed in 1963 from the flight crew of old air bases, lasted until 1991, when a reorganization was carried out.

In 1991, with the dissolution of the Soviet Union, Magadan Airport received international status, and the town gained exposure to the outside world with the inauguration of Alaska Airlines flights to the United States using Boeing 727 jets. In 1992, Aeroflot inaugurated nonstop service to Anchorage using Tupolev Tu-154 aircraft, and in 1994, this route was extended to provide same-plane one-stop service to Seattle. According to an anecdotal story published in The New York Times, the first Alaska Airlines flight needed deicing services, which were unavailable, so the flight crew acquired a quantity of vodka and sprayed it onto the wings. In 1995, the airline threatened to discontinue Russian service due to difficulties with contract workers. Alaska Airlines flights into Magadan and elsewhere in Russia were halted in October 1998 shortly after the 1998 Russian financial crisis, which rendered the routes unprofitable.

Aeroflot suspended flights to Sokol airport on 1 February 2009, due to the planned removal from service of the Tu-154 aircraft. Aeroflot cited the lack of certification of the airport in the acceptance and servicing of more modern aircraft, such as the Airbus A320 and Airbus A330, as the primary reason for the suspension of flights. It resumed service on 30 March 2009.

Flights between the Russian Far East and the United States have only been available for some periods. Alternative travel routes would be over Khabarovsk, Vladivostok, or other large Russian cities plus Beijing, Seoul or Tokyo.

Notably, Transaero's last flight prior to bankruptcy was operated from this airport to Moscow Vnukovo on 25 October 2015.

On December 20, 2024, the new terminal of Sokol Airport was opened. The first airplane to land was an S7 flight from Novosibirsk. The new terminal is equipped with 12 elevators, 2 escalators and 2 teletraps.