The airline was founded in 1998 when it moved its Air Operator's Certificate from the British Virgin Islands to Burundi.
[3] It started scheduled service with two Let 410s from Bujumbura to Beni, Bunia, Entebbe, Goma, Kigali, and Kigoma.
[4] The airline ceased all operations in 2000, however, no source for a declared bankruptcy has been found.
The IATA code for the airline was later re-used by Gol Linhas Aéreas Inteligentes in Brazil.
As of August 2006, the City Connexion Airlines fleet still included the following aircraft,[5] though no flights were being operated: