Восстание берберских племен против арабских пришельцев началось в Танжере и довольно быстро распространилось по всей Северной Африке. Посылаемые Омейядами для их усмирения отряды терпели поражения и, сильно потрепанные, возвращались в Андалусию. За одно десятилетие арабы почти полностью утратили власть в этой западной провинции и сумели удержаться только в отстроенных ими лагерях, из которых самым значительным был Кайраван, окруженный со всех сторон враждебными племенами.

Постепенно в провинциях Северной Африки начал распространяться ислам. На первых порах исламизация Магриба носила поверхностный характер. Берберы продолжали сохранять свои традиционные верования, хотя и увязывали их в какой-то мере с новым вероучением. Тем не менее со временем ислам в Северной Африке распространился повсеместно, с самого начала приняв форму хариджизма. Нет сведений о том, каким образом и кем хариджитская доктрина была занесена в Северную Африку, но ее эгалитарный характер попал на благоприятную, патриархальную почву берберского племенного общества, тем более что эта доктрина предполагала оппозицию к ненавистным сначала омейядским, а потом и аббасидским правителям. Постепенно вся Северная Африка оказалась хариджитской, что способствовало распространению и укоренению ислама, ибо по своим основным доктринам хариджизм мало чем отличался от учения суннитских традиционалистов.

Хариджизм сыграл в Северной Африке особую роль, придав традиционному стремлению берберов к самоограничению оттенок исламского пуританизма и ригоризма. Суннитские теологи создали в Кайраване знаменитую религиозную школу, которая способствовала распространению ислама на протяжении IX и X веков.

В VIII – IX веках на территории Северной Африки образовалось три независимых или полунезависимых от Багдада княжества: Идрисидов, Рустамидов и Аглабидов, в границах которых берберские племена вели весьма обособленную и почти независимую жизнь. Вокруг этих княжеств существовало множество племенных сообществ, стремившихся избежать чьего бы то ни было господства и продолжавших вести традиционный, сохранявшийся на протяжении многих веков образ жизни. Ислам лишь в минимальной степени затронул их верования, обряды и обычаи. Между этими племенами и племенными группами постоянно существовала известная враждебность, уходившая корнями в отдаленное прошлое, но никогда не перераставшая в открытые войны.

Следует отметить, что на раннем этапе распространения ислама в Северной Африке хариджитский эгалитаризм сосуществовал с особым почитанием потомков Пророка и членов его семьи. Видимо, берберским неофитам импонировали преследуемые на востоке Алиды, в чем, как и в склонности к хариджизму, проявилась их враждебная позиция по отношению к центральной власти. Поэтому многие Алиды, для которых жизнь на востоке как при Омейядах, так и при Аббасидах по политическим причинам стала невозможной, находили убежище в Магрибе и даже сумели завоевать авторитет и возглавить в религиозном отношении отдельные берберские племена. Наиболее известным среди них был основатель династии Идрисидов Идрис I ибн Абдаллах, внедривший в западной части Магриба шиитскую доктрину.

Идрис I ибн Абдаллах, правнук Хасана, сына халифа Али, принявший активное участие в восстании Алидов в Хиджазе в 786 году, еще во времена правления Харуна ар-Рашида бежал сначала в Египет, а оттуда в Марокко, где при поддержке нескольких берберских вождей, согласившихся признать его своим главой, в 789 году основал независимый шиитский эмират. Династия Идрисидов правила в Марокко до 905 года, когда страна была завоевана исмаилитской династией Фатимидов. При Идрисе I (789 –793) и сменившем его Идрисе II (793 –828) исламская культура стала быстро распространяться среди только что обращенных в ислам берберских племен, которые сумели сочетать старинный уклад жизни с исламской верой и практикой. Отделенный большим расстоянием от аббасидских центров эмират жил своей жизнью и не испытывал почти никакого давления со стороны багдадских властей.

При первых двух эмирах в Марокко, на месте старого римского города был выстроен Фес, который быстро рос, привлекая к себе множество мусульман из Андалусии и Ифрикии. Фес не только был столицей идрисидского эмирата, но довольно скоро после основания стал почитаться в качестве «священного города» шиитов, местопребывания многих алидских вождей. Однако вскоре после смерти Идриса II его многочисленные наследники поделили между собой власть над различными районами, эмират потерял былую силу, и в середине IX века очередной эмир вынужден был признать себя вассалом фатимидского махди Убайдаллаха, а спустя несколько лет фатимидские войска заняли Фес, и эмират утратил независимость.

Во второй половине VIII века в западной части Алжира образовался независимый эмират Рустамидов (777 –909), просуществовавший без каких-либо доктринальных или династийных конфликтов до фатимидского завоевания в 909 году. Основателем эмирата был некий Абд ар-Рахман ибн Рустам (777 –784), судя по имени, человек иранского происхождения. Рустамиды восприняли хариджитскую идеологию, которая была особенно популярна в VIII веке среди берберов Алжира, Южного Туниса и Триполитании. Однако, в отличие от единоверцев на востоке, алжирские хариджиты восприняли более умеренный ибадитский вариант учения, причем Ибн Рустам в 777 году был признан имамом всех ибадитов Северной Африки.

История образования хариджитского эмирата прослеживается в самых общих чертах. Овладев на сравнительно короткий срок Кайраваном, центром арабского господства в Северной Африке и оплотом традиционалистского суннизма, небольшая группа хариджитов-ибадитов бежала затем в Западный Алжир и основала вокруг города Тахарта в 761 году эмират. Тахарт был расположен на пересечении транссахарских караванных путей, и сложившиеся при Рустамидах обширные торговые связи обеспечили эмирату экономическое процветание.

Тахарт очень быстро стал одним из важнейших экономических и культурных центров Северной Африки. Сюда стекались жители самых разных африканских провинций, среди которых немалую роль играло христианское население Магриба, здесь процветали науки, и здесь побывали многие ученые и теологи из Андалусии. Рустамиды, оказавшиеся в окружении идрисидских шиитов на Западе и аглабадских суннитов на Востоке, пытались опереться на помощь кордовских правителей и установили с Андалусией широкие экономические и культурные связи. Смертельный удар эмирату нанесли Фатимиды, которые с установлением власти в Марокко вторглись в Тахарт, и с 909 года княжество Рустамидов утратило независимость.

Бóльшую лояльность по отношению к багдадским властям проявила ифрикийская династия Аглабидов. Еще в 800 году Харун ар-Рашид назначил наместником Ифрикии сына аббасидского военачальника в Хорасане аль-Аглаба – Ибрахима Ибн аль-Аглаба. Ибрахим обязался не только обходиться без материальной поддержки на содержание арабского гарнизона в провинции, но, напротив, уплачивать ежегодно в казну дань в размере 40 тысяч динаров, собираемых с подвластных ему земель в качестве налогов. На этих условиях Ибрахим Ибн аль-Аглаб сумел основать в Ифрикии небольшой полунезависимый эмират со столицей в Кайраване.

Династия Аглабидов правила в Ифрикии более ста лет (с 800 по 909 год), пока не была сметена Фатимидами. Ибрахиму ибн аль-Аглабу (800 –812) пришлось с первых же месяцев правления столкнуться с большим берберским восстанием, возглавляемым хариджитскими проповедниками, влияние которых было особенно сильным на юге страны. Энергичными действиями ему удалось добиться известного успокоения в провинции, а лояльным отношением к багдадским властям обрести почти полную независимость и право передавать власть по наследству в пределах своей династии. Позднее придворный историк египетских мамлюков Шихаб ад-Дин Нувайри (1279 – 1332) особо отметит в своей хронике, что «Ибн аль-Аглаб и его преемники передавали власть в стране кому хотели».