Plans for an airport on Nordkinnhalvøya were first articulated by a committee appointed by the Finnmark County Municipality. Their 1966 report recommended that six regional airports be built in Finnmark, which included Mehamn and Kjøllefjord as a possible site. Simultaneously the national government starting on planning a national network of regional airports. The Civil Aviation Administration (later renamed Avinor) looked into suitable sites at Mehamn, Kjøllefjord, and Gamvik. The government prioritized construction in Finnmark last, so the regional airline Norving took initiative to build smaller airfields in selected communities. They took contact with both Lebesby Municipality and Gamvik Municipality to initiate construction.

Initially the CAA supported Gamvik as a location for a regional airport, in part because of the lower investment costs. The municipal council in Gamvik instead chose the municipal center of Mehamn, 20 kilometers (12 mi) from Gamvik village. The Gamvik chapter of the Norwegian Red Cross Search and Rescue Corps started fund-raising for Gamvik village to build its own airport. It applied to the municipality, but no public funds were granted. Gamvik Airport opened on 29 August. Also at Kjøllefjord, 30 kilometers (19 mi) from Mehamn, locals decided to build their own airport. Kjøllefjord Airport opened in 1974, but because of the opening of Mehamn Airport it never saw any regular traffic. The use of the airports at Kjøllefjord and Gamvik fell out regular use from 1974 and were soon abandoned.

Simultaneously as Mehamn was awarded an airport, Parliament voted to build a new road, National Road 888, which would better winter transport between the villages of Kjøllefjord, Mehamn and Gamvik, allow Mehamn Airport to efficiently serve the entire peninsula. Construction was subcontracted to Veidekke. From they started construction in late 1973; it took 39 days from start until the first aircraft landed. Mehamn airport opened on 1 August 1974, at the same time as Sørkjosen Airport, Hammerfest Airport, Berlevåg Airport and Vadsø Airport. Because of late payment the airport remained owned by Veidekke until 1976. Both Widerøe and Norving applied to operate the Finnmark route, which would connect the airports together and to the primary airports in Finnmark and Tromsø Airport. Norving planned to operate with their Britten-Norman Islanders and Britten-Norman Trislanders. The government opted to selected Widerøe and their Twin Otters, citing the need for a single operator for all subsidized regional routes in the country.

Widerøe operated Twin Otters on the route until 1995, when the Dash 8 was introduced. The state and the Civil Aviation Administration took over ownership and operations of the airport from 1 January 1997, in exchange for 3.9 million kr being paid to Gamvik Municipality. Flights to Mehman have been subject to public service obligations since 1 April 1997. Airport security was introduced on 1 January 2005. The passenger terminal building has been expanded several times and a garage was built in 2005. The runway was expanded and a new lighting system was installed in 2011.

Future

Avinor sees a problem in getting new aircraft of the size of the Dash 8-100 (39 seats) which can use the 800 meter runways, so they plan to use smaller planes with 19 seats (which is the size of the Twin Otter) for these small airports when the Dash 8-100 retire before 2030.