Air Rhodesia Corporation se fundó el 1 de septiembre de 1967, mientras Rodesia del Sur se encontraba bajo aislamiento internacional. A diferencia de Zambia, Malaui mantuvo relaciones distendidas con Air Rhodesia Corporation, lo que permitió mantener y aumentar los vuelos entre Salisbury y Blantire; Air Rhodesia registró beneficios en su primer año de operaciones. Los aviones fueron repintados con una decoración que consistía en una parte superior blanca, con líneas de guía azul oscuro y azul claro en los laterales del fuselaje; también aparecían franjas inclinadas azul oscuro y azul claro en la aleta vertical. El controvertido "pájaro twiggi", una representación muy estilizada del ave de Zimbabue, emblema nacional de Zimbabue (entonces llamado Rodesia del Sur), se superpuso a las dos franjas de la aleta. Esto fue criticado en algunos círculos por ser difícilmente reconocible como un ave de Zimbabue, e incluso se comparó con un dhow árabe navegando.

Las ganancias de Air Rhodesia aumentaron entre 1969 y 1970, y la aerolínea mantuvo un buen desempeño a pesar de los desafíos derivados de las sanciones y el deterioro del clima político en Rhodesia. Se introdujeron servicios de pasajeros a Kariba; los servicios de los DC-3 a Wankie se modernizaron y comenzó a utilizar el Vickers Viscount; y se obtuvieron ingresos adicionales mediante el préstamo de tripulaciones excedentes a otras aerolíneas. Sin embargo, el rendimiento de Air Rhodesia se vio afectado cuando sus competidores comenzaron a utilizar nuevos aviones a reacción, y se hizo evidente que los aviones a reacción eran esenciales para los servicios internacionales. La aerolínea adquirió de forma encubierta sus primeros aviones a reacción, tres Boeing 720-025, que llegaron bajo un velo de secretismo la noche del 14 de abril de 1973, durante las vacaciones de Semana Santa. Inicialmente, fueron adquiridos por la aerolínea original Eastern Air Lines, una aerolínea estadounidense con sede en Miami, y posteriormente por Calair, una aerolínea chárter alemana que cerró en 1972. Los nuevos aviones a reacción de Air Rhodesia estaban listos para entrar en servicio en noviembre de 1973, justo cuando los precios del combustible subieron un 35% debido a la Guerra de Yom Kippur en Oriente Medio. Poco después, la guerra civil de Rodesia comenzó a intensificarse drásticamente, y la escasez de personal debido a los llamados a filas militares agravó las dificultades de la aerolínea. Mozambique obtuvo su independencia en 1975, y los servicios de Air Rhodesia a Blantire y Beira fueron prohibidos en marzo de 1976, cuando se prohibió a los aviones rodesianos sobrevolar territorio mozambiqueño. Hasta 1979, los únicos servicios externos de la aerolínea serían a Johannesburgo y Durban.

El 3 de septiembre de 1978, el vuelo 825 de Air Rhodesia, un Vickers Viscount con matrícula VP-WAS, fue derribado cerca de Kariba por terroristas nacionalistas. Solo ocho personas sobrevivieron al accidente y a la posterior masacre perpetrada por los guerrilleros. Tan solo cinco meses después, el 12 de febrero de 1979, el vuelo 827 de Air Rhodesia, otro Viscount con matrícula VP-YND, fue derribado en la misma zona, matando a todos los pasajeros a bordo. Como medida de protección, todos los Viscount de Air Rhodesia supervivientes fueron pintados rápidamente con una pintura mate especial de color verde amarillento, y todas las superficies metálicas brillantes del avión, incluidas las palas de la hélice y los conos, fueron repintadas. Para evitar que los misiles termoguiados se fijaran en los tubos de los reactores calientes, se instalaron protectores de motor especialmente diseñados en las góndolas, lo que aumentó significativamente el consumo de combustible del avión. Mientras tanto, debido a la guerra en curso, el número de pasajeros continuó desplomándose a medida que se disparaban los precios del combustible.

Cuando Rodesia alcanzó la democracia como Zimbabue Rodesia, Air Rhodesia se convirtió en Air Zimbabwe Rhodesia. En previsión de que la nueva tregua política trajera estabilidad y nuevas oportunidades, Air Zimbabwe Rhodesia ordenó la construcción de un nuevo y amplio hangar en 1979. Inmediatamente se pensó en reabrir rutas a destinos que habían estado cerrados a la aerolínea durante mucho tiempo debido a las sanciones.

Tras la independencia de Zimbabue, Air Zimbabwe Rhodesia pasó a llamarse Air Zimbabwe. Los servicios que conectaban Harare con Sudáfrica (Durban y Johannesburgo) ya operaban antes de la independencia del país. Los vuelos regulares comenzaron el 2 de abril de 1980 con destino a Londres-Gatwick. La compañía había alquilado un Boeing 707 a South African Airways hasta mayo de 1981, cuando adquirió tres Boeing 707 a Lufthansa. Ese mismo año, se inauguraron los vuelos a Fráncfort. La aerolínea registró una ganancia de 330.000 ZWL (220.000 libras esterlinas) en el ejercicio fiscal que finalizó el 30 de junio de 1980.

En la década de 1980, la aerolínea adoptó una nueva imagen de aeronave basada en los colores de la bandera de Zimbabue.

En 1982, se inauguró un servicio a Perth y Sídney, operado en colaboración con Qantas y operado con aviones Boeing 747SP de Qantas. En mayo de ese año, el Gobierno ordenó a Air Zimbabwe y a la aerolínea nacional de carga Affretair fusionar sus operaciones; la compañía de carga fue finalmente absorbida por Air Zimbabwe en julio de 1983. La aerolínea de carga continuó operando bajo la marca Affretair. Durante 1983, Air Zimbabwe se convirtió en miembro de la Asociación Internacional de Transporte Aéreo (IATA) y amplió sus rutas regionales a Gaborone, Lilongüe, Lusaka y Nairobi.

Para marzo de 1985, Air Zimbabwe contaba con 1443 empleados y su flota estaba compuesta por cinco Boeing 707-320B y siete Vickers Viscount. En ese momento, la aerolínea operaba servicios domésticos que unían Harare con Chiredzi, Bulawayo, Gweru, el Parque Nacional Hwange, Kariba, Masvingo y las cataratas Victoria, servicios regionales a Blantire, Durban, Gaborone, Johannesburgo, Lusaka y Nairobi, y vuelos intercontinentales a Atenas, Fráncfort y Londres; la ruta Harare-Perth-Sídney, ofrecida con aviones Boeing 747SP de Qantas, se operaba en asociación con Air Zimbabwe. Un Boeing 737-200 que había sido arrendado a Maersk Air fue devuelto al arrendador en 1986 y el primero de tres Boeing 737-200 propios se incorporó gradualmente y se puso en servicio en diciembre de ese año; el segundo y el tercer avión del tipo se entregaron en junio y julio de 1987. La capacidad adicional permitió extensiones de ruta a Dar es-Salaam, Manzini, Maputo y Mauricio. En 1987, la aerolínea adquirió un BAe 146-200 para rutas nacionales. También en 1987, la aerolínea anunció su intención de adquirir Ilyushin Il-62 y Il-86, así como Yakovlev Yak-42, en lugar de aviones de fabricación occidental. Estos planes nunca se materializaron, y Air Zimbabwe encargó dos Boeing 767-200ER. Con matrícula Z-WPE y nombre "Victoria Falls", el primer Boeing 767-200ER entró en la flota en noviembre de 1989. El Boeing 707 se retiró de las rutas de larga distancia poco después; estos aviones se siguieron utilizando para cubrir rutas regionales. El Vickers Viscount se retiró definitivamente del servicio en noviembre de 1989. La aerolínea incorporó gradualmente el segundo Boeing 767-200ER (Z-WPF, llamado "Chimanimani") a finales de 1990. En abril de 1995, se encargaron dos Fokker 50, que se entregaron un mes después.

En febrero de 2004, se reveló que la compañía había sido suspendida temporalmente por la IATA debido a deudas impagadas.^[2]​^[3]​ A finales de octubre de 2006, los precios de los billetes de Air Zimbabwe aumentaron hasta un 500%, en parte debido a que la inflación en el país superó el 1000% (en ese momento, el Banco Central de Zimbabue declaró que no podía seguir apoyando a Air Zimbabwe ni a otras empresas estatales con pérdidas) y en parte porque la aerolínea necesitaba divisas para pagar combustible, repuestos y catering.^[4]​ Una crisis cambiaria en el país provocó la cancelación de las operaciones de la aerolínea a finales de 2005, debido a la falta de divisas para pagar el combustible.^[5]​^[6]​^[7]​ En 2006, se reveló que el número de pasajeros había disminuido de 1 millón en 1999 a 23.000 en 2005.^[8]​

En mayo de 2011, la aerolínea fue suspendida nuevamente del sistema financiero y de reservas internacionales de la IATA debido al impago de las tasas de reserva. A principios de noviembre de 2011, se anunció que el gobierno absorbería una deuda de 140 millones de dólares estadounidenses para hacer la compañía más atractiva para los inversores extranjeros.^[9]​ Ya en diciembre de 2011, la aerolínea tenía dificultades para prestar sus servicios regionales e internacionales debido a la incautación de aeronaves por deudas impagadas.^[10]​^[11]​

En enero de 2012, la aerolínea quedó bajo administración judicial. Después de un fallido intento de reactivación, en el que los pilotos se negaron a reanudar los servicios nacionales por más de 35 millones de dólares en salarios y subsidios impagos, se anunció el 24 de febrero de 2012 que Air Zimbabwe quedaría en tierra indefinidamente.^[12]​ En marzo del mismo año, el gobierno de Zimbabue estableció Air Zimbabwe Private Limited como el nuevo propietario de la aerolínea después de disolver el antiguo propietario paraestatal de la aerolínea, Air Zimbabwe Holdings, y absorber una deuda de 150 millones de dólares.^[13]​ La aerolínea reanudó los vuelos de forma continua a principios de mayo de 2012,^[14]​ pero utilizando un solo avión y sirviendo solo a tres destinos nacionales (Bulawayo, Harare y las cataratas Victoria) y solo por un corto período de tiempo hasta la inmovilización de los aviones el 2 de julio de 2012.^[15]​ La aerolínea se reactivó a finales de noviembre de 2012, con un programa de vuelos reducido en la ruta Harare-Johannesburgo. Según informes, la aerolínea reanudó sus operaciones nacionales conectando Bulawayo, Harare y las Cataratas Victoria, así como la ruta regional a Johannesburgo, diariamente en abril de 2013,^[16]​ antes de la Feria Internacional de Comercio de Zimbabue de 2013.^[17]​ Aproximadamente 600 empleados de un total de más de 1000 habían sido despedidos a finales de mayo de 2013 como parte de las medidas de reducción de costos destinadas a recapitalizar la aerolínea.^[18]​ La Autoridad de Turismo de Zimbabue reveló en junio de 2013 que la cuota de mercado de la aerolínea sufrió una fuerte caída en el año que finalizó el 31 de diciembre de 2012, con una participación del 0,8% en este período, inferior al 27% del mismo período de 2009.^[19]​

En mayo de 2017, Air Zimbabwe fue incluida en la lista de aerolíneas prohibidas en la Unión Europea por no cumplir con las normas de seguridad de la UE.^[20]​

En julio de 2017, las deudas de Air Zimbabwe se estimaban en 330 millones de dólares estadounidenses.^[21]​ El 8 de junio de 2018, se informó que Air Zimbabwe tenía deudas de más de 300 millones de dólares y que ya no podía volar a la mayoría de los destinos debido a las amenazas de los deudores de incautar sus aeronaves.^[22]​ Con una deuda creciente y solo tres de sus aeronaves operativas, la aerolínea fue declarada bajo administración concursal el 6 de octubre de 2018.^[23]​

El 26 de marzo de 2020, la aerolínea se vio obligada a suspender todos los vuelos indefinidamente debido a la pandemia de COVID-19. Posteriormente, la aerolínea se vio obligada a suspender todos sus empleados sin sueldo y estaba en proceso de crear un plan maestro postpandemia.^[24]​^[25]​ Reanudó sus vuelos nacionales en septiembre y regionales en octubre de 2020.^[26]​

Para marzo de 2023, Air Zimbabwe informó haber liquidado su deuda con la IATA y esperaba reanudar los vuelos Londres-Harare.^[27]​^[28]​ Sin embargo, esto no ha llegado a materializarse.

En la actualidad (junio de 2025), Air Zimbabwe opera únicamente vuelos regulares a los siguientes destinos:^[29]​

La flota actual de Air Zimbabwe consiste en las siguientes aeronaves:^[30]​

En el pasado, Air Zimbabwe operó las siguientes aeronaves:^[31]​^[32]​

• Air Zimbabwe
• Air Zimbabwe North America Archivado el 19 de diciembre de 2008 en Wayback Machine.
• =UM&al_op=1 Flota de Air Zimbabwe (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).