The first aircraft to land in Brønnøysund was a Hansa-Brandenburg seaplane of the Royal Norwegian Navy Air Service on 23 July 1922. It was piloted by Hjalmar Riiser-Larsen and Finn Lützow-Holm, en route from Horten to Kirkenes. The following thirteen years Brønnøysund only saw occasional landings, when Norwegian Air Lines started a service from Bergen to Tromsø on 7 June 1935, which included a stop at the harbor in Brønnøysund. Passengers and mail would be rowed out to the waiting aircraft. The first season the route was flown using a single-engine Junkers W 34. The aircraft turned out to be too small and a larger Junkers Ju 52 was introduced the following season. Flights were dependent on good weather and were only operated during the summer. The route was taken over by Widerøe in 1938. All civilian flights were terminated during World War II, although the town would see occasional military landings.

Seaplane routes resumed in 1947 using the Junkers Ju 52. Construction of primary airports in Norway started in the 1950s based on building joint military and civilian airport with funding from the North Atlantic Treaty Organization (NATO). The alliance considered constructing an airport at Søndre Herøy in Herøy Municipality, an archipelago near Sandnesssjøen, but funding was never allocated to the project.

No primary airports had been built in Helgeland by the mid-1960s. The coastal parts of the region, such as at Brønnøysund, were without highways and railways. Although Widerøe operated a seaplane route, it remained a summer-only service. Travel time to Sandnessjøen, where the closest hospital was located, took five hours. A committee, led by Erik Himle and later Preben Munthe, was appointed in 1962 to consider additional airports in Norway. The Sud Aviation Caravelle jet aircraft was about to be phased into use on the main domestic routes by Scandinavian Airlines System and the committee recommended in 1964 that nine new airports be built which could serve jetliners, including an airport in Sandnesssjøen.

Widerøe came with an alternative proposal and suggested that a network of smaller airports be built instead, which could be served using short take-off and landing (STOL) aircraft. Smaller airports could be built and operated at lower costs than larger airports, but both airports and airlines would need subsidies to operate. Håkon Kyllingmark was appointed Minister of Transport and Communications in 1965 and was a proponent of the STOLport proposal. The political rationale was that, despite that the total operating costs would rise, that it would provide better services to rural areas and thus keep up their population. The regional airports were built in groups, and the first four were built in Namsos and Helgeland.

Planning started in 1966 and construction commenced the following year. Brønnøysund Airport cost NOK 2.7 million plus costs for expropriation and navigational aids. NOK 1.9 million was covered by the state, while the rest was covered by Brønnøy Municipality. The runway was originally 800 meters (2,625 ft) and was the only asphalted area in Brønnøysund. The airport was originally operated by the municipality, except the tower, which was operated by the Norwegian Telecommunications Administration. Brønnøysund was one of very few regional airports to receive a restaurant. The airport opened on 30 May 1968, along with Mo i Rana Airport, Røssvoll, Namsos Airport, Høknesøra and Sandnessjøen Airport, Stokka. Widerøe commenced flights to Bodø and Trondheim with their de Havilland Canada DHC-6 Twin Otters the following day.

The first year of operation saw 6,157 passengers, dropping to 5,543 in 1969. Originally there were two southbound and two northbound flights per day in the summer and one per direction during winter. In 1969 this increased to two flights per direction all year. Trønderfly started an air ambulance service in the early 1970s. Widerøe introduced the de Havilland Canada Dash 7 in 1982, resulting in the terminal being expanded. Offshore helicopter services began the following year. The runway was expanded to 1,000 meters (3,281 ft) in 1987.

Offshore helicopter operations commenced out of Brønnøysund Airport in 1981, when Helikopter Service was contracted to fly to the exploration field on Trænabanken. A combined fixed-wing and helicopter hangar was completed in 1983. The contract changed to Lufttransport in 1984. Operations remained limited and in 1989 the airport only saw 34 helicopter flights. The exploration resulted in a positive finding on the Norne field, which started production in 1997. Norsk Helikopter, later renamed Bristow Norway, established a helicopter base at Brønnøysund Airport in 2002 and took over flights to the Skarv Oil Field.

NATO showed interest in upgrading Brønnøysund Airport in 1991. Specifically, they intended to spend NOK 125 million in expanding the runway to 2,000 meters (6,562 ft) and building a fuel depot. The airport was planned used as a relief military airbase without any permanently stationed aircraft. The plans were canceled in 1993 following cutbacks in NATO. Widerøe introduced Dash 8 aircraft in 1992, gradually replacing the Dash 7.