The airline was established on 26 April 1991 as KLM exel on a co-operational base with Dutch national carrier KLM. Scheduled flights were launched on 1 May of the same year. On 6 November 2004, the co-operation with KLM was ended, and the airline became Air Exel. One month later, in December 2004, Air Exel's Chief Executive Officer, Harm Prins, was arrested on charges of fraud, blackmail, and money laundering. The investigation let to the surfacing of financial difficulties with Air Exel, which was subsequently shut down on 31 January 2005.