The first official proposals for an airport at Kjøllefjord were launched by a Finnmark County Municipality-appointed committee which in published a report in 1966.

[1] The airline therefore contacted the municipality in December 1969 and proposed that an airfield be built within a year, which it could operate with its Britten-Norman Islander aircraft.

Norving applied for permission to operate taxi route flights, but this was rejected by the Ministry of Transport and Communications because it would drain part of the catchment area of Mehamn Airport.

Kjøllefjord Airport became disused during the 1980s, although both the runway and terminal remain, in a dilapidated state.

[6][7] A simple shed was used as a terminal, which included waiting areas for passengers and radio equipment.