The airline was established and started operations in 1948, as Newfoundland Airways operating float-equipped aircraft from a base in Gander, Newfoundland on charter, mail and freight work to northern Newfoundland and Labrador. Since then the base of the company has moved to Goose Bay. It was purchased in 1983 by Provincial Investments Inc., owned by Roger Pike, along with associate company, Labrador Aviation Services Ltd. Air Labrador was owned by the Pike Family, but then taken over by Philip Earle in 2010. Air Labrador conducted a fantasy flight in the 1990s with a Santa Claus visit on board while it taxied the tarmac. In March 2009, the company announced they were ceasing flight service to Montreal due to financial trouble. Airline service ended in Newfoundland in May 2009, two months after announcing the shut down of Montreal operations. The airline now continues to fly within Labrador and Quebec, as well as St. Anthony, Newfoundland and Labrador.
On February 3, 2012, the company announced that the Nunatsiavut Government bought a 51% share in Air Labrador.