Не довольствуясь властью над Египтом, Сирией и Палестиной, Ахмад ибн Тулун начал вмешиваться в придворные интриги Багдада. В 883 году он даже пытался лишить аль-Муваффака власти и предложил аль-Мутамиду план побега, дабы тот получил возможность избавиться от опеки брата. Незадачливый халиф двинулся было из Самарры в путь, но был перехвачен в дороге отправленным регентом отрядом и водворен обратно в Самарру. Позднее Ахмад ибн Тулун собрал в Дамаске группу улемов, которые по его подсказке объявили, что халиф аль-Мутамид пленник брата и не обладает свободой действия. Впрочем, это решение не имело никаких последствий.
В 884 году на вершине своей славы Ахмад ибн Тулун умер и, как это становилось обычаем в автономных провинциях Халифата, пост эмира унаследовал его двадцатилетний сын, Хумаравайх (884896). Новый эмир, как и его отец, правил самовластно и еще в меньшей мере считался с регентом аль-Муваффаком. К этому времени аль-Муваффак сумел справиться с восстанием занджей и мог себе позволить новую попытку подчинить непокорную провинцию. Узнав о смерти Ахмада ибн Тулуна, он двинул в Египет армию, но потерпел новое поражение. В результате он оказался вынужденным узаконить наследственную власть Тулунидов и признать Хумаравайха и его потомков правителями Египта и Сирии на условии уплаты ими дани. Имя аль-Муваффака должно было упоминаться в пятничной молитве «дабы, как говорилось в соглашении, страна не попала в руки неверных и шиитов», а следующий халиф, сын аль-Муваффака, чтобы закрепить отношения с Тулунидами, женился на дочери Хумаравайха.
В последние десятилетия VIII века перестают подчиняться багдадским властям и провинции Северной Африки. К сожалению, мало что известно о взаимоотношениях арабских завоевателей и коренного населения этой отдаленной области на начальном этапе арабского господства. По всей видимости, завоеватели проявляли здесь большую жестокость, чем в восточных провинциях. Возможно, это объясняется тем, что в Магрибе они нашли не общество с организованными и налаженными связями, но разрозненные племена, которые не считали цивилизованными и потому высокомерно третировали. Отсюда та враждебность, с которой берберы встречали арабов в 740 году и позднее.
Восстание берберских племен против арабских пришельцев началось в Танжере и довольно быстро распространилось по всей Северной Африке. Посылаемые Омейядами для их усмирения отряды терпели поражения и, сильно потрепанные, возвращались в Андалусию. За одно десятилетие арабы почти полностью утратили власть в этой западной провинции и сумели удержаться только в отстроенных ими лагерях, из которых самым значительным был Кайраван, окруженный со всех сторон враждебными племенами.
Постепенно в провинциях Северной Африки начал распространяться ислам. На первых порах исламизация Магриба носила поверхностный характер. Берберы продолжали сохранять свои традиционные верования, хотя и увязывали их в какой-то мере с новым вероучением. Тем не менее со временем ислам в Северной Африке распространился повсеместно, с самого начала приняв форму хариджизма. Нет сведений о том, каким образом и кем хариджитская доктрина была занесена в Северную Африку, но ее эгалитарный характер попал на благоприятную, патриархальную почву берберского племенного общества, тем более, что эта доктрина предполагала оппозицию к ненавистным, сначала омейядским, а потом и аббасидским правителям. Постепенно вся Северная Африка оказалась хариджитской, что способствовало распространению и укоренению ислама, ибо по своим основным доктринам хариджизм мало чем отличался от учения суннитских традиционалистов. В результате в районе Такарта появились первые магрибинские исламские теологи.
Хариджизм сыграл в Северной Африке особую роль, придав традиционному стремлению берберов к самоограничению оттенок исламского пуританизма и ригоризма. Суннитские теологи создали в Кайраване знаменитую религиозную школу, которая способствовала распространению ислама протяжении всего IX и X веков.
В VIIIIX веках на территории Северной Африки образовалось три независимых или полунезависимых от Багдада княжества: Идрисидов, Рустамидов и Аглабидов, в границах которых берберские племена вели весьма обособленную и почти независимую жизнь. Вокруг этих княжеств существовало множество племенных сообществ, стремившихся избежать чьего бы то ни было господства и продолжавших вести традиционный, сохранявшийся на протяжении многих веков образ жизни. Ислам лишь в минимальной степени затронул их верования, обряды и обычаи. Между этими племенами и племенными группами постоянно существовала известная враждебность, уходившая корнями в отдаленное прошлое, но никогда не перераставшая в открытые войны.
Следует отметить, что на раннем этапе распространения ислама в Северной Африке хариджитский эгалитаризм сосуществовал с особым почитанием потомков Пророка и членов его семьи. Видимо, берберским неофитам импонировала судьба преследуемых на востоке Алидов, в этом, как и в склонности к хариджизму, проявилась их враждебная позиция по отношению к центральной власти. Поэтому многие Алиды, для которых жизнь на востоке как при Омейядах так и при Аббасидах по политическим причинам стала невозможной, находили убежище в Магрибе и даже сумели завоевать авторитет и возглавить в религиозном отношении отдельные берберские племена. Наиболее известным среди них был основатель династии Идрисидов Идрис I ибн Абдаллах, внедривший в западной части Магриба шиитскую доктрину.
Еще во времена правления Харуна ар-Рашида хасанид Идрис I ибн Абдаллах, правнук Хасана, сына халифа Али, принявший активное участие в восстании Алидов в Хиджазе в 786 году, бежал сначала в Египет, а оттуда в Марокко, где при поддержке нескольких берберских вождей, согласившихся признать его своим главой, в 789 году основал в северной части страны независимый шиитский эмират. Династия Идрисидов правила в Марокко до 905 года, когда страна была завоевана исмаилитской династией Фатимидов. При Идрисе I (789793) и сменившем его Идрисе II (793828) исламская культура стала быстро распространяться среди только что обращенных в ислам берберских племен, которые сумели сочетать старинный уклад жизни с исламской верой и практикой. Отделенный большим расстоянием от аббасидских центров эмират жил своей жизнью и не испытывал почти никакого давления со стороны багдадских властей.