De maatschappij werd in 2012 opgericht door Hamid Kerboua samen met investeerder Lex Versteeg. Hamid Kerboua richtte eerder de luchtvaartmaatschappijen Amsterdam Airlines, is in november 2011 failliet gegaan, en Denim Air, failliet in 2010, op.[1] Op 20 november 2012 maakten Maastricht en de provincie Limburg bekend dat de maatschappij 330.000 euro subsidie krijgt.[2] Op 15 januari 2013 is de ticketverkoop gestart. Maastricht airlines zou starten op 23 maart 2013 met vliegen op haar routes. Tot op heden heeft zij echter nog geen AOC (vliegvergunning) en is vluchtuitvoering onmogelijk.
Maastricht Airlines zal haar vluchten beginnen met twee Fokker 50-toestellen. Deze worden gekocht van Air Baltic. In het voorjaar van 2013 ontvangt Maastricht Airlines een derde Fokker 50, die 'standby' komt te staan. De toestellen krijgen Nederlandse registraties. Omdat de twee toestellen van Air Baltic in het verleden bij KLM Cityhopper hebben gevlogen zullen de toestellen de oude registratie terugkrijgen (PH-KVA en PH-KVB).