Die dann von Rwandair eingesetzte MD-82 wurde von Acvila Air (Rumänien) gemietet. Es wurde vor der Anmiete der MD-82  gemeldet, dass Rwandair Express ihre bescheidene Flotte um eine Boeing 737-300 erweitern könnte, die von KLM übernommen werden soll. Die bei Rwandair Express eingesetzte MD-82 bot 142 Passagieren (12 First/130 Economy) Platz und ab 2006 kommt auch eine Dash 8-200 ergänzend zum Einsatz. Luftverkehr in Ruanda war über Jahre nahezu nicht existent. 1994 wurde Ruanda weltbekannt, da sich in diesem Land (und in Burundi) ein Genozid ereignete, den man eigentlich für nicht mehr möglich hielt und die Welt schaute zu, während sich Menschen zermetzelten. Die Anzahl an täglich getöteten Menschen erreichte absolute Spitzenwerte und die Region ist auch heute noch ein Unruheherd.

Anfang Mai 2007 tauchen Fotografien einer Boeing 737-500 mit der Information auf, dass Rwandair Express mit dieser 737 ihre angemietete MD-80 ersetzt hätte und die 737-500 von Air Malawi angemietet sei. Diese Meldung bestätigte sich und die MD-80 wurde an Acvila Air retourniert.

Mitte September 2007 mehren sich Gerüchte, dass Rwandair Express wieder ein MD-80-Betreiber werden könnte, da die AKFED (Aga Khan Fund for Economic Development) in der jüngsten Vergangenheit mehr oder weniger die Kontrolle über Rwandair Express übernommen hat oder übernehmen wird und die AKFED insgesamt bis zu sieben MD-87 an afrikanische Fluggesellschaften ausliefern wird. Die Dachgesellschaft der Fluggesellschaften Air Burkina, Air Uganda und C.A.M. Compagnie Aerienne Du Mali unter der Kontrolle der AKFED ist die "Celestair"-Gruppe.