Die Fluggesellschaft wurde 1947 unter dem Namen South West Air Transport gegründet. Im Jahr 1959 wurde sie mit Oryx Aviation unter dem Namen Suidwes Lugdiens (Afrikaans für Südwest Luftdienst) bzw. South West Airways zusammengeschlossen. Die kleine Fluggesellschaft Namib Air wurde 1966 eine Tochtergesellschaft von Suidwes Lugdiens. Im Jahr 1978 wurde der Name der gesamten Gruppe zu Namib Air geändert. Im Jahr 1982 erwarb die südafrikanische Regierung die Aktienmehrheit und erklärte Namib Air zur Hauptfluggesellschaft des damals von Südafrika verwalteten Südwestafrika. Im Jahr 1989 fanden erste direkte Flüge mit der Boeing 737 zwischen Windhoek, Johannesburg und Kapstadt statt. Die Unabhängigkeit Namibias 1990 ermöglichte eine Ausdehnung des Flugbetriebs, seit diesem Jahr wird Frankfurt am Main angeflogen. Seit 1991 trug die Fluggesellschaft den Namen Air Namibia.

Für die Bedienung von Langstreckenzielen leaste man 1990 eine Boeing 747SP von South African Airways. Diese Maschine wurde 1998 durch eine Boeing 767-300 ersetzt. 1999 erwarb Air Namibia eine Boeing 747-400M Combi; neben Passagieren konnte so auch Fracht zugeladen werden. Als sich diese Maschine als zu groß und damit auch zu unwirtschaftlich erwies, wurde sie verkauft und durch zwei geleaste McDonnell Douglas MD-11 abgelöst, diese wiederum nur wenige Monate später durch zwei von BCI geleaste Airbus A340-300. Mitte 2009 wurden die Flüge nach London-Gatwick eingestellt. Seitdem war Frankfurt das einzige europäische Ziel der Gesellschaft. Seit Mitte Dezember 2009 bot Air Namibia sein neues, voll automatisiertes Vielfliegerprogramm mit dem Namen reward$ an. Es basierte auf dem Sammeln von Meilen und entspricht damit, samt einer nötigen Registrierung bei Air Namibia, den üblichen Vielfliegerprogrammen der großen internationalen Fluggesellschaften. Parallel und noch bis Januar 2010 bot Air Namibia ein manuelles Programm an, das auf dem Sammeln von Bordkarten basierte und Rabatte oder Upgrades ermöglichte.

Ende Januar 2011 gab Air Namibia bekannt, dass zwei fabrikneue Airbus A319-100 die beiden Boeing 737 auf den Regionalstrecken ersetzen. Diese wurden im Januar 2013 ausgeliefert. Es handelt sich um die ersten Flugzeuge in Besitz von Air Namibia seit etwa 20 Jahren. Mitte März 2012 wurde zudem bekanntgegeben, dass die beiden Airbus A340-300 durch zwei Airbus A330-200 ersetzt werden. Im September 2013 wurde eines dieser Flugzeuge dem neuen Besitzer ausgeliefert. Am 16. Juni 2014 stand Air Namibia kurz vor dem Erlöschen ihrer Betriebslizenz durch die International Civil Aviation Organization (ICAO), da das Management diese nicht rechtzeitig verlängern ließ. Es wurde kurzfristig ein Aufschub gewährt und die Lizenz ist schließlich nicht verfallen. In dem Zusammenhang wurden die Geschäftsführerin und der Flughafenbetriebsleiter von Air Namibia entlassen.[6] Die Leitung der Fluggesellschaft hatte am 28. Juni 2014 amtierend der Schweizer Luftfahrtexperte René Gsponer übernommen. Er war zuvor bereits COO.[7][8] Ende Juli 2015 wurde er von dem Amt enthoben und am 12. August 2015 Mandi Samson als amtierende Geschäftsführerin eingesetzt.[9] Sie gab ihr Amt im März 2019 auf und wurde interimistisch durch CCO Xavier Masule ersetzt. Er trat von dem Posten des Interims-CEO am 10. Februar 2020 zurück. Neuer amtierenden Geschäftsführer wurde der CHRO Elia Erastus.

Im Februar 2020 stellte Air Namibia ihre ehemals lukrativste (von 1998 bis 2015) Verbindung von Windhoek nach Luanda in Angola ein. Am 6. Juli 2020 teilte das Verkehrsministerium die Aussetzung der Lizenz von Air Namibia zum 9. Juli 2020 mit. Bis zum 23. Juli 2020 hatte die Gesellschaft Zeit, die nötigen Finanzmittel aufzubringen. Ansonsten sollte die Lizenzen endgültig widerrufen werden. Das Obergericht in Windhoek stimmte in einem Eilverfahren in der Nacht auf den 9. Juli Air Namibia zu und erlaubt vorerst den Weiterbetrieb. Am 3. Februar 2021 trat Air Namibia an die Öffentlichkeit und versprach die Einstellung aller unlukrativen Strecken (d. h. aller außer denen von Windhoek nach Katima Mulilo, Rundu, Ondangwa und Walvis Bay) und die Nutzung der eigenen sechs Flugzeuge. Sieben Tage später wurde die Liquidierung und Einstellung des Betriebes verkündet. Am 26. Februar 2021 wurde die Fluggesellschaft vorläufig vom Obergericht liquidiert. Am 26. März 2021 wurde die Insolvenz und Liquidierung von Air Namibia durch das Gericht, ohne Einsprüche, genehmigt.

Am 28. April 2021 wurden die beiden Langstreckenflugzeuge vom Typ Airbus A330-200 nach Leipzig überführt und an den Leasinggeber Castlelake übergeben. Die frühzeitige Rückgabe der Maschinen kostet den namibischen Staat 1,6 Milliarden Namibia-Dollar und damit N$ 667 Millionen weniger als die Leasingkosten bei regulärer Beendigung des Vertrages.[20] Die zwei Langstreckenflugzeuge vom Typ Airbus A330-200 wurden im November 2021 via Zürich zum Flughafen Lourdes überführt. Dort sollen die beiden Flugzeuge zeitnah verschrottet werden. Ein weiterer Airbus A319-100 steht immer noch in Windhoek. Im Oktober 2021 unterbreitete ein südafrikanisches Startup, BDS Airways, ein Kaufangebot für die insolvente Air Namibia in Höhe von 3,2 Milliarden Namibia-Dollar. Das Angebot wurde im Januar 2022 auf 1,4 Milliarden Namibia-Dollar reduziert.

A319-100

A330-200

A340-300

B737-200

B737-500

B747-400

B747-sp

Beech 1900

EMBRAER-135/145

MD-11

B737-800

B767