Cependant, le Maghreb était gagné par l'hérésie kharédjite, venue d'Orient, et dont les doctrines égalitaristes, par opposition aux prétentions légitimistes des gouverneurs arabes, issus de l'aristocratie qurachite, a séduit les Berbères. Le calife pouvait, non seulement être choisi en dehors de Quraych et même des Arabes, mais il devait avoir une conduite irréprochables, d'appliquer à la lettre les principes coraniques et pratiquer la justice. Autrement, les fidèles devaient le combattre et le mettre à mort. Vaincus en Orient, où ils avaient commis des excès, les Kharédjites ont trouvé refuge au Maghreb. Ils parviennent à soulever les Berbères contre les gouverneurs qui les traitaient avec mépris. La révolte, partie de Tanger, se répand rapidement. Après avoir remporté de francs succès sur les armées arabes, les Kharédjites sont battus mais parviennent à maintenir des positions stratégiques. Sous la direction d'Abû al Khottab ‘abd al A'la ben al-samah, ils s'emparent de Tripoli, puis de de Kairouan, en 758. Un noble d'origine persane, ‘Abderrahaman Ibn Rostum, est nommé gouverneur de la ville. Mais à la mort Abû al Kottab, Ibn Rustom évacue l'Ifriqya pour le Maghreb central, plus sûr.
