During the German occupation of Norway during World War II, the German Wehrmacht was dependent on supplies to the town of Kirkenes which had to be shipped past Varanger Peninsula. The convoys were the target of bombardments from the Soviet Air Force, stationed close by on the Kola Peninsula. Originally the convoys were protected by the German Jagdgeschwader 5 based at Alta Airport. With an increasing number of raids, the Luftwaffe decided to build two airfields on Varangerhalvøya, Berlevåg and Vardø Airport, Svartnes

The Wehrmacht had become aware of the favorable location when two aircraft had performed an emergency landing at Storsletta in 1941. Construction at Berlevåg started in August 1943 and the airport received a 950-meter (3,120 ft) mixed concrete and wooden runway. The airfield received a detachment of fighter aircraft from JS5, including the Focke-Wulf Fw 190. A radar was installed on a hilltop close to the airport in 1944. The airport was demolished with the German retreat from Finnmark in 1944. The wooden runway was subsequently pillaged by locals to accumulate building materials for reconstruction.

Use of the airport area as a civilian airport was launched by Varangfly director Odd Bentzen in 1964. After visiting Iceland he proposed a series of short and simple airports in Finnmark which could serve the airline's air ambulance service. A different proposal was launched in 1966 by several of the larger airlines, including Scandinavian Airlines System, Braathens SAFE and Widerøe, to establish a network of short take-off and landing airports in rural areas; Berlevåg was one of six original proposals for Finnmark. A county committee was established in 1966 to look into building small airfields in Finnmark, including Berlevåg. In the following years the municipality made investments to allow the airfield to be used for air ambulance services. Part of the motivation was Berlevåg's poor port conditions, which often forced seaplanes to land at Kongsfjord.

Norving (previously Varangfly) started offering flights to the closed-down military airport in 1970 using their newly delivered Britten-Norman Islander. The background was a landing at the airfield to transport a baby to Kirkenes Hospital. The Civil Aviation Administration stated that they were not opposed to building smaller ambulance airports, but that the state's priority was constructing a network of regional airports. The service started off with a daily round trip ordered by the district physician; patients had priority, but the airline would transport other passengers as well. After a month a second daily round trip was introduced.

State funding was allocated, allowing the airport to be upgraded. The regional airport opened on 1 August 1974, the same day as four other airports in Finnmark. Both Widerøe and Norving applied to operate the subsidized regional routes in Finnmark, which included the route to Berlevåg. Widerøe was awarded the contract in 1973. Because of the steadily more regular flights to Berlevåg, Norving applied to the government for permission to operate these as taxi routes. While the airline had been forced to operate its taxi service on the time specifications of the customer, taxi routes would allow the airline to operate feeder services with timetables. No such permission was granted. Widerøe took over operations from 1 August 1974 using the de Havilland Canada Twin Otter. On 14 November 1980 the garage and workshop burned down; a new building was built and opened in 1982. The passenger terminal was expanded in 1988 with a new arrivals and departure hall. Widerøe introduced the Dash 8 in 1994. The state and the Civil Aviation Administration took over ownership and operations of the airport from 1 January 1997, in exchange for 2.2 million Norwegian krone (NOK) being paid to Berlevåg Municipality. Airport security was introduced on 1 January 2005.