Air Rwanda founded by the government of Rwanda on 15 July 1975 as the national airline of Rwanda. The airline began operations on domestic flights and to neighbouring nations, with a network including flights from Kigali to Gisenyi, Kamembe, Bujumbura and Ostend. Other services were also operated to Tanzania, Uganda and Zaire, along with a scheduled cargo flight from Bujumbura to Mombasa in Kenya. A fleet comprising one Boeing 707, two de Havilland Canada DHC-6 Twin Otters and one Piper Aztec was operated on these routes. The airline would also occasionally lease a Britten-Norman Islander for operations from the Rwandan Air Force. The airline was implicated in a mooted deal with Libya, under which the Libyans would paint Boeing aircraft belonging to Libyan Arab Airlines in Air Rwanda livery. The purpose of the deal was to allow the Libyans to skirt an embargo and to gain access to spare parts for the aircraft. The possible deal came to light when the United States gained photos of some Libyan aircraft being repainted in Air Rwanda livery, after which the Rwandans cancelled talks with the Libyans.
In 1994, the airline was forced to cease flying to domestic destinations because of the Rwandan Genocide, whilst internationally the airline reduced its network to include only Kigali, Bujumbura and Entebbe. In 1996, the airline was renamed to Rwanda Air and its fleet consisted only of the Boeing 707. By this time its network had increased to include Gisenyi, Kamembe, Bujumbura, Ostend, Dar es Salaam, Entebbe and Kinshasa.
In November 1997, it was announced that Alliance Express, the regional arm of multi-national Uganda-based airline SA Alliance Air, had reached a deal with the Rwandan government to take over the operations of Rwanda Air, after which it would operate as Alliance Express Rwanda from 1 March 1998. The new airline would operate on routes from Kigali to Entebbe, Kinshasa, Johannesburg and Nairobi with Boeing 737-200 equipment. The government continued to hold a majority 51% share in the airline, with Alliance Air taking a 49% stake. The airline began operations to Bujumbura in neighbouring Burundi on 8 February 1999. In its first year of operations Alliance Express Rwanda posted a US$4 million operating loss on US$6 million revenues, which the airline blamed on its inability to operate flights to the Democratic Republic of the Congo due to the Second Congo War. A dispute between Rwanda, Uganda and the Democratic Republic of the Congo, according to the airlines' deputy managing director, meant the Kigali-Lubumbashi-Kinshasa route could not be developed. By this time, the airline was also operating a Bombardier Dash 8 in addition to the 737. After the Ugandan-based SA Alliance Air ceased operations in October 2000, the Rwandan government entered into an agreement with South African Airways to ensure the Rwandan subsidiary would continue to operate. Operations continued until the company was eventually wound up on 30 November 2002 and its operations taken over by Rwandair Express, later to be rebranded as RwandAir.
- Guttery, Ben R. (1998). Encyclopedia of African airlines. Ben Guttery. p. 152. ISBN 0-7864-0495-7. Retrieved 2009-10-14.
- "Air force (Rwanda), Air force". Jane's Information Group. 6 July 2009. Retrieved 16 January 2010.
- "Tiny Rwanda must tackle giant problems". The Montreal Gazette. 13 April 1983. pp. I1. Retrieved 16 January 2010.
- Yates, Chris (12–18 November 1997). "Alliance spreads into Central Africa". Kampala: Flight International. p. 14. Retrieved 16 January 2010.
- "Alliance Express". Flight International. 4–10 February 1998. p. 13. Retrieved 16 January 2010.
- "African turf fight". Airline Business. 1 January 1998. Retrieved 16 January 2010.
- "Rwandan airline begins flights to Burundi". Kigali: Radio Rwanda. 8 February 1999. Retrieved 16 January 2010.
- "Alliance blames Congo problems for loss". Flight International. 27 October – 2 November 1999. p. 24. Retrieved 16 January 2010.
- Wakabi, Michael (3 November 1999). "Connecting East Africa". Kampala: Flight International. Retrieved 16 January 2010.
- Wakabi, Michael (17 October 2000). "$50 million losses forces Alliance Air to close". Kampala: Flight International.
- "ALLIANCE EXPRESS (RWANDA) 0./100 (Rwanda), AIRLINES". Jane's Information Group. 9 August 2007. Retrieved 16 January 2010.