Following the deregulation of aviation in Norway in 1994, Coast Air started several regional routes, replacing its fleet with Jetstream 31 aircraft.

From 2000, Coast Air also served Florø Airport on public service obligation with the Ministry of Transport, using ATR 42 aircraft.

From 1999, Coast Air started competing direct with the larger airlines on main routes, and introduced new regional and international services.

The company was a local mechanical and small-plane operator until 1984, when it started to apply for concessions to perform regional airline services in Norway.

[1] Following the 1984 decision by Scandinavian Airlines System to discontinue their route from Haugesund to Aberdeen in the United Kingdom, Coast Aero Center applied for the concession.

[5] In October 1984, Coast Aero Center, along with Norving and Fonnafly, applied for concession for the routes from Stord Airport, Sørstokken to Oslo, Bergen, and Stavanger.

[6] Coast Air was successful at receiving the concession, and service started on 12 August 1986 with a ten-seater Beechcraft Super King 200.

[9] Additional concessions to fly to Haugesund were also granted the same year,[10] as were direct services to Oslo, making the stops in Skien unnecessary.

[15] The company was thrown into financial distress on 7 February 1988, when Den norske Creditbank (DnC) announced that they would not issue more credit.

[18] On 17 February, a proposal for refinancing was made, where the hangars were sold to the local municipalities, who would also make a guarantee for NOK 2 million.

[22] The following year, Coast Air also received the concession for operating the subsidized routes to the newly opened Fagernes Airport, Leirin.

[38] The company received NOK 51 million annually, from 1 April 2000 to 31 March 2003; this resulted in there no longer being in intermediate stops from Florø to Bergen and Oslo.

[42] In January 2000, Braathens decided that it would terminate its service from Oslo to Røros Airport, as well as reducing the number of flights between Haugesund and Bergen.

Coast Air therefore announced it would increase the number of departures between Haugesund and Bergen, and at the same time was willing to fly to Røros if a state subsidy was granted.

[64] With the freeing up of aircraft after the 2003 PSO contract losses, Coast Air introduced and additional daily flight to Aberdeen.

Using the ATR planes, Coast Air started with two daily round services between Haugesund and Oslo Airport, Gardermoen.

[74] On 16 February, Coast Air also started competing with Braathens and Widerøe on the route between Stavanger and Bergen, marketing it as a low-fare service and ticket prices as low as NOK 199.

[76] In March 2004, Coast Air was forced to close the Stord to Oslo route, after several reductions in frequency during the past year.

[77] To create more inertia on the Bergen–Stavanger route, Coast Air also started a cooperation with DAT, where the latter flew an extra daily round trip.

[79] In December, the Norwegian Competition Authority started investigating Scandinavian Airlines for illegal price dumping on the Oslo–Haugesund route.

The authority suspected that SAS had illegally cross-subsidized the route to fend off the competition,[80] and announced the company would be fined NOK 20 million.

[82] Though initially appealed by the authority, the matter was settled out-of-court in December 2007, in which the airline agreed that they had broken the law, but that since it happened just after the act came into power, they would not have to pay the fine.

[83] On 23 November 2004, eighteen local investors founded the airline Vildanden to start scheduled flights from Skien Airport, Geiteryggen.

[86] Norsk Hydro, who have a lot of employees in the Grenland area, stated that they could not start using Vildanden because they had an agreement to use SAS Braathens' services from Sandefjord.

[88] By September, the most popular departures were being fully booked, and Vildanden asked Coast Air for a larger aircraft, with about 30 seats.

[89] An agreement with Danish Air Transport (DAT) to operate an ATR 42, with a capacity of 48 seats, was signed by Vildanden in mid October.

[90] To be able to breach the agreement with Coast Air—who still had a wet leasing contract, but were not able to put into operation a larger aircraft—the company Skien Lufttransport AS was created, and it purchased all the revenue and passenger rights from Vildanden.

Coast Air chose to continue operating the route between Bergen and Skien in their own name, and used the same aircraft and slot times.

[113] DAT offered to purchase the three ATR 42 aircraft, and hire part of the crew who lost their jobs as a consequence of the bankruptcy.

[116] With the fall of Coast Air, Stord Airport was without any scheduled routes and income, and lost NOK 350,000 per month until a new service was in place.