Mainland Air was established in 1991 by Queenstown businessman Christopher Kelliher. From 1995 to 2006 the airline operated courier flights for New Zealand Post between Dunedin and Christchurch. Later in 2007 the airline started a thrice weekly Dunedin to Alexandra and Queenstown service using a ten seater Piper Chieftain.  In March 2008 Mainland started a thrice weekly Dunedin to Invercargill service also using its Piper Chieftain aircraft. At that time Mainland were also considering services to Wanaka and Te Anau. Later all these scheduled services were dropped due to lack of demand. Late 2009 Chris Kelliher sold the company to the Paterson family who owned Mainland’s major maintenance provider, Southair Ltd 
Mainland Air also operates a flying training school, called Mainland Aviation College.
A new scheduled service began on 4 June 2014 linking Oamaru and Christchurch using Piper Chieftain aircraft. Oamaru had been without an air service since Eagle Airways pulled out in 1 January 2010. Flights to Timaru are to be considered as the airline has been approached by members of the business community. The airline has been asked to do a Wanaka to Christchurch and a Oamaru to Wellington route.