Air Mauritius a été créée le 14 juin 1967 par Amédée Maingard, un agent de manutention. Grâce à ses relations, il trouve des partenaires tels qu’Air France et la BOAC qui s’allient au gouvernement et à Rogers & Co. Ltd pour lancer la compagnie nationale d’aviation. La première réunion du conseil d'administration de Air Mauritius est tenue dans les locaux de Rogers et Amédée Maingard est nommé président, fonction qu’il assumera jusqu’en 1981.
Le premier vol international de la compagnie fut organisé en juin 1967, entre Maurice et la Réunion et effectué avec un Piper Navajo PA-31 de six places, loué à Air Madagascar. Ses opérations furent étendues par la suite à l'ile Rodrigues, toujours avec le même appareil en aout 1972. En 1977, Air Mauritius loua un Boeing 707 à British Airtours pour ses vols internationaux. Au cours des années 1970 et 1980, la compagnie a exploité un Boeing 707 et des Boeing 747, pour ses vols longs-courriers. Tout les 747 ont été déclassés et ont depuis été remplacés par des Airbus A340 acquis à partir de 1994, ainsi que par des Boeing 767 acquis en 1988, un ATR 42 acquis en 1997, un ATR 72 introduit en 2002 pour les liaisons entre les îles des Mascareignes et des Airbus A319 pour les vols moyens-courriers sur le continent africain. Air Mauritius fut la première compagnie aérienne de l'hémisphère sud à voler avec des A340. D'ailleurs la compagnie s'est fait livrer en décembre 2006, deux nouveaux Airbus A340-300E de nouvelle génération.
Le transporteur est également l'une des rares compagnies aériennes dans le monde (avec Aeroflot, British Airways et Air Sahara) à combiner les services aériens avec des hélicoptères de vols, en utilisant la gamme d'hélicoptères de Bell Aircraft Corporation. Ce service d'hélicoptères est utilisé pour des excursions dans l'ile, le transfert de passagers de l'aéroport vers leur hôtel...
En 1988, l'un des deux Boeing 767-200ER a établi un nouveau record de distance de vol sans escale pour un bimoteur lors du vol de Halifax, en Nouvelle-Écosse, vers l'île Maurice. La distance parcourue était 14 042 km et le vol à duré 16 heures et 27 minutes.
En 1995, la compagnie fut cotée à la Bourse de Maurice. La compagnie est détenue par Air Mauritius Holding (51%), par l'État (19,97%), Port-Louis Fund (6,32%), The State Investment Corporation (4,72%), le gouvernement de Maurice (4,53%), Rogers et compagnie (4,28 %), British Airways (3,84%), Air France (2,78%) et Air India (2,56%). Elle emploie 2761 personnes (en Mars 2007). La compagnie est une des plus grandes entreprises de l'île et participe grandement à l'économie du pays et au développement du tourisme à l'île Maurice. Pour une petite population d'environ 1,2 millions de personnes, Air Mauritius est généralement considérée comme étant une assez grosse compagnie aérienne internationale. En mars 2007, Air Mauritius est devenue la première compagnie aérienne d'un pays d'Afrique australe à voler avec flotte de moyens et longs courriers composée uniquement d'Airbus.
