The airline was established in August 1974 as a flight training and charter operator. Scheduled airline operations began in 1980. In the 1980s, the company also developed its airborne maritime surveillance division, which operated until 1989 as Atlantic Airways. In 1988, it acquired Eastern Flying Service (established in 1956 and operating an extensive air courier network). In 1995, it created an Interprovincial Airlines division to operate scheduled airline operations and entered into a commercial agreement with Air Nova. It is a partner, with the Innu Development Limited partnership, in Innu Mikun Airlines, which serves the Labrador coast.

Traditionally, the company operated light aircraft such as Piper Navajo's and the Britten-Norman Islander around Atlantic Canada. Eventually, the airline began operating DHC-6 Twin Otters and Fairchild Metroliners and, at one point, had a Convair 580 in its fleet. In 2001, PAL took the delivery of its first Saab 340 aircraft. This meant that PAL Airlines had become a 705 carrier, as per Transport Canada Canadian Aviation Regulations, which meant that the first class of flight attendants were trained at this time. The airline added to its 705 fleet three years later when the company was awarded the VALE Inc. contract for the Voisey's Bay Mine in Labrador. This contract required the use of de-Havilland Dash 8's which began to arrive in 2004. Provincial eventually added more Dash 8's as part of the airline's scheduled air service.

...
Wikipedia