The airline was established in 1996 as Reguljair and operated domestic services using an Embraer EMB 110 Bandeirante until its operating licence was revoked on 14 November 2000. The airline was relaunched as Nordic East, dba Flynordic.com on 1 December 2000. In November 2003 Finnair acquired 85% of the shares and the remaining 15% in May 2004, when a new subsidiary company, Nordic Airlink Holding, was established. In October 2004 the airline was rebranded as FlyNordic. Finnair placed FlyNordic into bankruptcy in 2005, although operations of the reorganised company, Nordic Airlink Holding, doing business as FlyNordic, continued as usual. It has 240 employees (at March 2007).
On 24 April 2007 Norwegian Air Shuttle announced that they had bought 100% of the FlyNordic shares from Finnair. This makes Norwegian Scandinavia's largest low-cost airline. As a result of Finnair's ownership in FlyNordic, Finnair now owns 5% of Norwegian Air Shuttle.