Nigeria Airways ging im Juni 1958 aus der West African Airways Corporation hervor und hatte ihren Sitz in Lagos.
Mit vorerst Boeing B-377, Douglas DC-3 und später Comet-4, die durch Unterstützungsmaßnahmen der britischen BOAC zur Nigeria gelangten, nahm man den Flugverkehr auf.
Ab 1961 kamen B-707 zur Flotte und man bediente nicht nur London, sondern unter anderen auch Dubai, Frankfurt / Main, Jeddah, Kinshasa und Lagos.
Weitere Flugzeugtypen die Nigeria einsetzte waren Vickers Viscount und VC-10, Airbus A-310, Fokker F-27 und F-28, Boeing B-727, B-737, B-747, B-767 und Douglas DC-8 und DC-10.
Ab 1993 wurde für ein Jahr eine neue Bemalung an einigen Flugzeugen getestet, jedoch ging man schnell wieder zum alten Livre zurück.
Anfang 2002 musste Nigeria Airways wegen fehlendem Versicherungsschutzes der Flotte ihren Flugverkehr einstellen. Hier spiegelte sich die hoffnungslose Überschuldung der Gesellschaft wieder.
Im Jahr 2003 kam es zur Liquidation, welches zu Unruhen der Belegschaft wegen ausstehender Löhne führte.
Die britische Virgin Group zeigte Interesse und es kam zu Verhandlungen die in einer umfangreichen Umstrukturierung der ehemaligen Gesellschaft gipfelten.
Der Neuanfang war zum 28. Juni 2005 beschlossen und die neue Airline im Land hieß von diesem Zeitpunkt an Virgin Nigeria.