Khārijitisk berbisk modstand mod det arabiske styre
Det politiske liv i Maghrib i det 8. århundrede var domineret af modsætningen i de arabiske herskeres position, som, mens de udgav sig for at være forkæmpere for en religion, der anerkendte alle troendes lighed, understregede deres etniske særpræg og udøvede deres autoritet med ringe respekt for de islamiske religiøse normer. Denne modsigelse kom til overfladen i deres forhold til berberne, efter at sidstnævnte blev muslimer i stort antal – især ved at tjene i den arabiske hær, som vides at have inkluderet berbiske kontingenter, da den var under kommando af Ḥassān ibn al-Nuʿmān og hans efterfølger Mūsā ibn Nuṣayr. Mange berberkrigere deltog i erobringen af Spanien i 711. Selv om de bekender sig til islam, blev de behandlet som mawālī (“klienter”) af de arabiske stammer og havde derfor en lavere status end de arabiske krigere og modtog mindre løn end disse. Desuden var det kun den arabiske herskende klasse, der høstede frugterne af erobringen, som det tydeligvis var tilfældet i Spanien. Krigernes klager fremhævede berbernes vrede i almindelighed, som skyldtes en praksis som opkrævning af menneskelig tribut hos berberstammerne, hvorved den arabiske herskende klasse blev forsynet med slaver, især kvindelige slaver. ʿUmar II (717-720) var den eneste umayyadiske kalif, der vides at have fordømt opkrævningen af menneskelig tribut og beordret, at den skulle afskaffes. Han sendte også 10 tābiʿūn (“tilhængere”; disciple af profeten Muhammads ledsagere) ud for at undervise berberne i islam. Denne fromme kalifs oplyste politik overlevede dog ikke hans korte regeringstid. Den bidrog snarere til at bekræfte muslimernes overbevisning i Maghrib om, at islam ikke kunne sidestilles med det umayyadiske kalifherredømme.
Den muslimske Khārijite-sekt udnyttede dette revolutionære potentiale i deres kamp mod det umayyadiske styre. Khārijitisk doktrin appellerede tilsyneladende til berberne, fordi den afviste det arabiske monopol på det politiske lederskab af det muslimske samfund, understregede fromhed og lærdom som de vigtigste kvalifikationer for samfundets overhoved og sanktionerede oprør mod overhovedet, når han handlede uretfærdigt. I 740 udbrød der et stort berberoprør mod det arabiske styre i Tanger-området. Den første leder var en berber ved navn Maysara, der var kommet til Kairouan under indflydelse fra Ṣufriyyah, den ekstremistiske gren af den khārijitiske sekt. De berbiske oprørere opnåede en forbløffende militær succes mod den arabiske hær. I 742 havde de overtaget kontrollen med hele Algeriet og truede Kairouan. I mellemtiden havde Ibāḍiyyah, som udgjorde den moderate gren af den khārijitiske sekt, overtaget kontrollen med Tripolitanien ved at omvende de berberstammer, der boede der, især Hawwāra og Nafusa, til deres doktrin. Ibāḍīs dominans i Tripolitanien var et resultat af dāʿīs (“propagandister”), der blev sendt fra gruppens hovedcentrum i Irak, efter at det khārijitiske oprør dér var blevet undertrykt af den umayyadiske hær i 697.
Umayyadernes kalifale herredømme i Maghrib sluttede i 747, da Fihriderne, ʿUqbah ibn Nāfiʿs efterkommere af ʿUqbah ibn Nāfiʿ – som benyttede sig af umayyadernes optagethed af ʿAbbāsid-oprøret, der førte til deres fald – greb magten i Ifrīqiyyah. Fihrid-dynastiet kontrollerede hele Tunesien undtagen den sydlige del, som på det tidspunkt var domineret af berberstammen Warfajūma, der var associeret med Ṣufrī Khārijitterne. Fihridernes herredømme ophørte i 756, da Warfajūma’erne erobrede den nordlige del af landet og indtog Kairouan. Umiddelbart derefter proklamerede Ibāḍiyyah i Tripolitania imidlertid en af deres religiøse ledere som imam (den khārijitiske ækvivalent til sunniekaliffen) og i 758 erobrede de Tunesien fra Ṣufriyyah. Der opstod således en Ibāḍī-stat omfattende Tunesien og Tripolitanien, som varede, indtil ʿAbbāsiderne, efter at have konsolideret deres autoritet som kaliffer i Mellemøsten, sendte en hær til regionen i 761 for at genoprette kalifstyret i Maghrib.
Den ʿAbbāsiderne kunne kun påtvinge deres autoritet i Tunesien, det østlige Algeriet og Tripolitanien. Deres guvernørers autoritet i den rekonstruerede wilāyah i Ifrīqiyyah blev hæmmet, fordi de var afhængige af en hær, der overvejende blev rekrutteret blandt de uregerlige arabere i provinsen. Efter at de arabiske tropper gjorde mytteri mod den ʿAbbāsiske guvernør i 800, blev Ifrīqiyyah omdannet til et arabisk kongerige, der blev styret af Aghlabid-dynastiet i ʿAbbāsiske kalifers navn. Dynastiets grundlægger, Ibrāhīm ibn al-Aghlab, havde indtil da haft kommandoen over den arabiske hær i det østlige Algeriet. Efter at have brugt sine tropper til at genoprette ro og orden i Tunesien, etablerede han sig som hersker over provinsen. Kaliffen Hārūn al-Rashīds accept af Ibn al-Aghlabs tilraning af autoritet var knyttet til sidstnævntes fortsatte anerkendelse af ʿAbbāsids overherredømme og betaling af tributter til Baghdad.
