Originally the airport had two runways, 1,600 and 1,200 meters (5,200 and 3,900 ft) long, respectively, but the smaller was closed in 1996 when the longer was extended.

The first aircraft to land in Sør-Varanger was part of a trial undertaken in 1922 by the Royal Norwegian Navy Air Service to test the flight time from Horten to Kirkenes.

The mission was awarded to Hjalmar Riiser-Larsen and Finn Lützow-Holm, who chose to fly the 45-hour trip along the coast.

The first scheduled service started to Kirkenes the following summer with postal flights to Tromsø flown by Widerøe on behalf of Norwegian Air Lines (DNL).

From 26 September 1940, three weekly services were operated from Trondheim to Tromsø, with two of these continuing to Kirkenes, using a 16-passenger Junkers Ju 52.

The damage proved easy to repair and by January 1945, both troops of Norwegian police officers from Sweden led by Bernt Balchen and the Soviet Air Forces could land at Høybuktmoen.

[7] The first service after the war was started by DNL on 13 October 1945 and flew to Tromsø, with onwards connection to Trondheim and Oslo.

[8] The service only lasted until 1948, when it was replaced with a Ju 52 seaplane route with intermediate stops at Vadsø and Hammerfest to Tromsø.

From 1954 the route was taken over by Widerøe, who introduced smaller Noorduyn Norseman and de Havilland Canada DHC-3 Otter aircraft.

The Widerøe seaplane service was flown on behalf of DNL and later Scandinavian Airlines System (SAS) and remained until 1963.

[9] Varangfly later also bought an eight-seat aircraft which offered flights to Lakselv and Bardufoss, and to Ivalo Airport in Finland, where it connected to Finnair's service to Helsinki.

Although Kirkenes was included in the plan[9] construction was placed on hold, both because of high costs and because other airports further south had to be completed before or at the same time.

Work consisted of expanding the east–west runway to 1,600 meters (5,200 ft) and building a new passenger terminal and control tower; the latter two were not completed in time for the opening.

[12] SAS introduced the 52-passenger Convair Metropolitan on their domestic services, while Finnair served the airport with the 30-seat Douglas DC-3 on their flights to Finland.

[13] Busy Bee was contracted by the Norwegian Armed Forces to fly military charters in June 1968.

They had two 50-passenger Fokker F27 Friendships stationed at Høybuktmoen and flew two daily services from Kirkenes and other locations in Northern Norway to Bodø, with onwards connection to Stavanger and Oslo on Fridays.

[14] To serve the regional services Widerøe originally operated twenty-passenger de Havilland Canada aircraft.

At the same time the ministry and SAS started looking at the airport structure in Finnmark, as all the services in the county were in need of subsidies.

SAS was flying a 90-seat aircraft two to three times per day between Kirkenes and Alta with only ten to fifteen passengers.

[16] Emergency meetings were being held between SAS Commuter and the ministry by June 1990 because of low regularity and many cancellations.

[17] Non-transfer flights from Kirkenes to Oslo were reintroduced on 1 April 1992, albeit with the services stopping at Tromsø.

[19] Aeroflot started two weekly services between Kirkenes and Murmansk and onwards to Arkhangelsk Airport in June 1990.

[13] The extensions never received operating permit from the Civil Aviation Authority of Norway as there are two hills which hinder aircraft landing from the east to follow a safe final approach.

SAS bought Braathens in 2002, resulting in the latter taking over the service and increasing to two daily flights to Oslo.

[13] Widerøe reopened its Murmansk service in August 2007,[25] but low patronage caused the airline to terminate the route from December 2008.

The terrain is actually flatter to the east, but because the runway was expanded in that direction, the extension cannot be used without removing all ground in the twelve-degree slope.

For instance, during winter a 180-seat 737-800 can only utilize 71 percent of its permitted take-off weight; this would hinder fully loaded aircraft flying further than Oslo.

[45] Norwegian Air Shuttle is building a unified fleet of 737-800 aircraft and will only be able to serve the airport during winter if the investments are carried out.