Les troubles religieux, ajoutés aux troubles politiques, devaient accélérer la ruine de l'Empire romain. Des villes comme Thamugadi ou Thévesta seront détruites. Au cours de la restauration, les Byzantins, tenteront de les relever, en les fortifiant : mais la présence romaine connaissait désormais ses derniers jours. A la fin du VIIe siècle de l'ère chrétienne, de guerriers venus d'Orient, porteurs d'une nouvelle religion, apparaissent à l'est. Cette arrivée va susciter une forte résistance des populations de l'Aurès, dont le territoire servait de passage aux nouveaux conquérants. Les insurrections se succéderont. L'une des premières sera menée par Kussila, le chef de la puissante tribu des Awraba. En guerre contre les arabes, il avait fini par faire sa soumission puis par se convertir à l'Islam (675). Il a réussi également à gagner la confiance du chef musulman Abû al Muhadjîr Dinâr en devenant l'un de ses proches collaborateurs. Mais l'arrivée, en 681, de ‘Uqba Ibn Nafi'ê, le brutal conquérant de l'Afrique du Nord, allait bouleverser la donne. Il traite avec mépris Kusila en le faisant couvrir de chaînes et le traîne comme un trophée vivant à travers le Maghreb.
