Aurès Aviation est créée en 2000, sous l'agrément portant le numéro 001 délivré par la Direction de l'aviation civile et de la météorologie (DACM)[6], par Abdelmajid Louai[7]. Elle est la première école algérienne professionnelle de pilotage du secteur privé[8].
Au cours des 10 années suivant sa création, l'école est soumise à un boycott de la part de l'État algérien, qui opte pour les écoles étrangères[6]. En 2010, le ministre des Transports algérien, Amar Tou prend la décision de former les pilotes des compagnies commerciales algériennes en Algérie, au sein d'Aurès Aviation[9],[4]. La même année, les compagnies Tassili Airlines[9],[4],[10] et Air Algérie[11],[9] signent un contrat avec l'école pour la formation de leurs pilotes.