Selskabet blev grundlagt i 1946 som South West Air Transport og begyndte at flyve i 1948. I 1959 blev selskabet omdøbt til South West Airways. South West fusionerede med Namib Air i 1978, hvor navnet Namib Air blev bevaret. Den namibiske stat fik aktiemajoriteten i selskabet i 1982, og selskabet opnåede dermed status som Namibias nationale flyselskab. I forbindelse med landets uafhængighed i oktober 1991 fik selskabet sit nuværende navn. I 1990erne benyttede man et Boeing 747 på flyvninger til Europa. Fra 2004 overgik man til et McDonnell Douglas MD-11 på samme rute, ligesom man i 2005 også tilføjede en Airbus A340-300. I starten af september 2006 købte Air Namibia sit andet A340-300.
