Andøya Air Station was built with North Atlantic Treaty Organization funds as a combined Supreme Allied Commander Europe and Supreme Allied Commander Atlantic project as a base for maritime surveillance. Construction started in 1952 and all installations not required to be physically located at the air station were placed at Skarsteindalen, 12 kilometers (7 mi) away. Andøya became the base for the 333 Squadron, which initially operated the Grumman HU-16 Albatross. These were replaced by the Lockheed P-3 Orion in 1969. Construction and further expansion of the air station resulted in the villages of Haugnes being expropriated. Construction was prohibited from 1953, but the expropriation was not carried out until 1971.

With the establishment of the air station, plans arose to take advantage of the infrastructure for civilian flights. The airport's location made it suitable to serve Vesterålen, although it was located at the northern tip of the archipelago. SAS started serving Andenes from 1964 with their 56-seat Convair Metropolitans, which consisted of three night flights with intermediate stops at Bodø Airport and Bardufoss Airport before continuing to Oslo Airport, Fornebu. The night flights caused difficulties corresponding with the flights as there was a limited ferry and bus service during night. The Sud Aviation Caravelle was introduced on Northern Norway flights from 1965 and later these were replaced with the Douglas DC-9.

It soon proved difficult to provide sufficient patronage to keep operations profitable. With the opening of a network of short take-off and landing airports elsewhere in Central Hålogaland in 1972, Widerøe started serving the airport using the de Havilland Canada Twin Otter. SAS retained a small number of Oslo flights until 1976, when they withdrew from the service. At the time the military chartered aircraft for their own needs, so Andøy Mayor Johan Kleppe took initiative to coordinate the civilian and military routes, without the military supporting the proposal.

Parliament decided in 1982 that Andenes would be the base for operating helicopters offshore to oil installations off Troms. However, when operations commenced operations flew out of Tromsø Airport because of the difficult weather conditions at Andenes. Operations were moved to Hammerfest Airport following the discovery of Snøhvit. Widerøe introduced the larger, 50-seat de Havilland Canada Dash 7 in 1981, followed by the Dash 8 between 1993 and 1995. The routes were made subject to public service obligations with the Ministry of Transport and Communications from 1 April 1997. Widerøe won the initial tender. A proposal to make Andenes an international airport was launched in 2000, which also proposed that the airport change its name to Lofoten Airport. Unlike the two airports in Lofoten, Leknes Airport and Svolvær Airport, Helle, Andenes is able to handle jetliners. The name change was rejected by interests in Lofoten, which accused Vesterålen of stealing the more well-known Lofoten name.

From 1 April 2003 Norwegian Air Shuttle took over the route from Andenes to Bodø and Tromsø. However, they decided to terminate their operations with the Fokker 50, and thus also serving Andenes, to concentrate their efforts on becoming a low-cost carrier. From 1 January 2004 the route was served by Widerøe, who won the extraordinary tender. The state paid NOK 68 million for 27 months, up 25 percent from the Norwegian bid, including a service from Tromsø to Lakselv Airport, Banak. The tender for the three years starting on 1 April 2006 was won by Coast Air, which used an ATR-42 on the route. Coast Air was not able to make money on the route and abandoned the PSO contract from 1 April 2007. Widerøe won the subsequent tender and started flights from that date. Norwegian started irregular scheduled flights to Oslo Airport, Gardermoen, using the Boeing 737-800 from June 2012.