Després del genocidi de Ruanda de 1994 el govern va prendre diversos intents de reactivar l'antiga aerolínia nacional Air Rwanda que va cessar les operacions durant el genocidi. Diverses empreses privades van mostrar interès en associar-se amb el govern i amb la companyia SA Alliance Air va dirigir la companyia des de 1997 fins a 2000.[3] Després de la cessació d'operacions de SA Alliance, el govern de Ruanda es va fer càrrec de les operacions ruandeses i va tornar a reflotar l'aerolínia per garantir la seva continuïtat. RwandaAir va començar a operar l'1 de desembre de 2002 com a nou operador nacional per a Rwanda sota el nom de "Rwandair Express" (amb el transport aeri de passatgers com a activitat principal).
A l'abril de 2007 Rwandair Express va llogar un Boeing 737-500 d'Air Malawi. Aquest avió va ser detingut a l'Aeroport Internacional de Kigali, aparentment com a part d'una disputa de contracte. Al novembre de 2008, Rwandair va arribar a un acord per llogar un Boeing 737-500 d'Air Namíbia, que va permetre a Rwandair reprendre els vols a Johannesburg, que s'havien cancel·lat a l'abril de 2008.
Rwandair Express ha perdut l'acord de codi compartit amb Kenya Airways en la ruta Nairobi/Kigali. Rwandair ha expressat la seva intenció de reprendre els acords de codi compartit i ampliar vols a Nairobi.
Al desembre de 2008, Rwandair Express planejava ampliar la seva xarxa de rutes regionals per incloure destinacions com Dar es Salaam, Addis Abeba, Mwanza, Lusaka i Kinshasa.
El 2016, Rwandair va rebre l'auditoria de seguretat de l'IATA per a operacions de terra (ISAGO).[4]
Destinacions
RwandAir serveix les següents destinacions (inclosos destins de codi compartit) el febrer de 2018:[5][6]