Ат-Табарі вказує на спробу перевести в Пн. Африці прийнявши іслам представників підкорених народів на сплату хараджа, що викликало ті ж самі наслідки, що і в Іраці. В цей самий рік був вбитий Ісезид ібн Абу Муслім в Іфрикії, а він був її намісником. Причиною цього було те, що він вирішив вчинити з жителями Іфрикії згідно зі звичаєм ал-Хаджжаджа ібн Юсуфа в відношенні людей ісламу, які жили в містах. Після його вбивства правителем було поставлено намісника, що був над ними до нього. Це був Муххамед ібн Іязид. Він був у війську Іязида Ібн Абу Мусліма [30; 189].
Ще одне джерело характеризує ставлення до берберів влади на місцях. Згідно з ним, бербери відправляли делегацію до халіфа Хімама з проханням розібратися з їхніми скаргами на намісника і амілей, її очолював Майсара. Джерело говорить: «Хариджити внесли в середовище жителів Іфрикії незгоду, що існує до цього часу» [30; 190]. Вони домагалися, щоб їх вислухали, але це виявилося важким завданням і тоді вони пішли до ал-Абшару. З претензією на те, що їх емір ходить в походи разом з ними, але коли до нього потрапляє здобич, то він віддає її в розділ без їх участі. Коли вони повернулися в Іфрикію, то повстали проти аміла халіфа Хішама, вбили його і заволоділи Іфрикією [15; 25].
З фактів приходу делегації в столицю до халіфа можна зрозуміти, що берберське населення ще вірило в можливість знайти справедливість, обирало діяти мирно.
В 740 р. намісником Пн. Африки була розпочата велика експедиція в Сицилію. Велика частина війська була залучена в цю експедицію, що слугувало сигналом для загального повстання, що охопило райони від Танжера до Тлемсена. Повсталі відмовлялись визнавати владу халіфів [30; 191].
Війська з сицилійського походу були терміново відізвані, з Сирії та Єгипту було надіслано майже 30 тисяч добре озброєних військових. Повстанська армія складалась з погано озброєних, напівроздягнених берберів. Але вони нанесли своїм супротивникам поразку, заманивши їх вглиб країн і відокремивши кінноту від піхоти. Згодом повстанці рушили в Кайруан двома арміями. Кайруанському наміснику вдалося роз’єднати їхні сили і нанести їм в 742 р. завершальний удар [30; 192].
Повстання берберів мало великі наслідки – воно відіграло важливу роль в зміщенні династії Омейядів, послабивши її військову могутність і залишивши державну казну без значних податкових надходжень.
За своїм розмахом берберське повстання було найбільшим за всю історію халіфату [30; 180].
Оцінка хариджитських повстань має значення для характеристики всього історичного процесу історичного розвитку в Пн. Африці, тому вона необхідна.
Народні повстання охоплювали і інші провінції халіфату. Повстання почалися навіть в Сирії і Середній Азії.
Хариджити в Пн. Африці не лише боролися проти жорстоких і неприйнятних форм експлуатації. Вони намагалися створити суспільство за стародавнім зразком, на принципах первісної демократії. Весь рух мав релігійну форму, і нове суспільство сприймалось як релігійна община.
На чолі хариджитських общин були або місцеві релігійні авторитети, або особи, що були наступниками пророка, його родичів чи прихильників, або вожді місцевих напівкочових племен, що намагалися забезпечити собі владу в невеликій області.
Таким чином, хариджитські повстання призвели, по-перше, до відсторонення влади халіфських намісників; по-друге, до проявів ініціативи народних мас, на чолі яких інколи знаходилися вихідці з простих станів народу, а не лише племінні вожді. Але і в одному, і іншому випадку це призводило до утворення харижитиських держав. Їх поява спостерігається в середині VІІІ ст.
Отже, араби за два століття завоювань захопили чималі території у Північній Африці. Основними причинами військових успіхів, отриманих арабами, були економічний занепад і різке загострення соціальних протистоянь в цих державах.
Кінець VІІІ – початок ІХ ст. ознаменувались повстаннями, що відбувалися в Єгипті і Пн. Африці.
Головною причиною виникнення нових держав в Пн. Африці слід вважати загальний хід історичного розвитку в тих районах, де не було впливу культурних центрів прибережних районів чи воно було мінімальним. Ці райони були ізольовані, райони високих плато, західні області Магрибу. Там існувала тенденція – намагання вождів до закріплення своєї влади. Це складало такі соціально-політичні організми, які в подальшому могли б розвиватися в напрямку складання ранньокласових держав. Подібні організми повинні бути виділені, як протодержави [30; 190].
Після виступу Мабсари повстання хариджитів продовжувались періодично протягом 32 років, і влада на Сході часто відправляла війська на їх придушення. Вони отримували перемогу не щоразу, але після кожного повстання територія під владою халіфів в Пн. Африці зменшувалась. Велике значення при цьому мав той факт, що проти арабського джунда виступали кочівники зената, що заселяли в той час Південні території цивілізованих областей. Вже поразка в 741 році означала кінцеву втрату Далекого Магрибу. Після цього до хариджицького руху приєдналось все населення до самого Туніса. Воно припинило підкорятися представникам халіфату і постійно їх тривожило. Кайруан потрапив до берберів.
Коли Аббасиди захопили владу, вони намагались повернути втрачені землі. В 760 р. в Африку був надісланий з військом Ібн ал-Амас, а в 772 р. – Іязид ібн ал-Хатім. Але жодному з них не вдалося помирити владу багдадських халіфів далі області Заб. Всі області, розміщені на захід від мерідиану Бужи, стали незалежні і на їх території виникло доволі багато берберських держав, населення яких не підкорялося арабам, хоча і залишалися мусульманами. Вже в 744 р. правнук Укби ібн Нафі, Абд ар-Рахман іблн Хабіб, переправився в Африку з Іспанії і заволодівши Іфрикією вигнав Олийядського намісника. Правління його і його сім’ї продовжувалося до 757 р. Згодом управління Іфрикією і Кайруаном на протязі року і двох місяців знаходилося в руках берберів варфаджума, які були хариджитами-суфритами. Після цього хариджити-ібадити з Джебель-Нафуса прогнали варфаджума, які були хариджитами-суфритами. Після цього хариджити-ібадити з Джебель-Найфуса прогнали варфаджума і були володарями Триполітанії і Іфрикії на протязі двох років. Вождь ібадитів Нафуса Абу-ін-Хаттаб призначив намісником в Кайруан водного з ібадитів, Абд ар-Рахман ібн Рустема, який був в Кайруані з 758 р. по 761 р. вигнаний звідти новим аббасидським намісником, Абд ар-Рахман ібн Рустем втік в Центральний Магриб і на Високому плато заснував місто Тахарт, де в 762 р. був обраний імамом ібадитської общини і став засновником Рустемідської династії, яка налічувала вісім імамів і проіснувала до початку Х ст. [25; 42].
До 777 р. Абд ар-Рахман був визнаний імамом всіх ібадитів Магрибу і опинився на чолі великої держави. Його сину і насліднику Абд ал-Ваххабу до кінця століття вдалося підкорити всі берберські ібадитські племена. Його влада простягалась від Тріполі до Тлесмена і від берега моря, де знаходилися міста Марса Фаррух і Марса-ель-Хараз (між Азревом і Мостаганемом) до оазисів Уед-Рір і Уаргла. Області Заб і Ходна, разом з горами Аурас, які також були заселені ібадитами, з’єднували західні території рустемідської держави з областями Південного Тунісу і Північно-західної частини Тріполітанії. З’явилася нова держава-община хариджитів-ібадитів і найбільше з ібадитських держав [30; 190].
Держава хариджитів-ібадитів зі столицею в Тахарті була найбільша на території Алжиру. На чолі держави була сім’я рустемідського походження. Рустеміди вважалися керівниками ібадитів всього Магрибу [22; 222].
До моменту складання хариджитських держав в Пн. Африці іслам якщо і не закріпився, то знаходився в процесі закріплення. Тут також склалися стереотипи відносин з владою, і ці стереотипи мали за приклад систему, що склалася на основі установ, введених разом з ісламом. Держава Рустемідів будувалася на основі ідей хариджитів, основних принципів іслама і соціальних зв’язків родо-племінного ладу. Це прослідковуєтсья на прикладі організації ібадитської держави в Тахарті. Коли ібадити оселились в Тахарті, їх керівники зібрались для вирішення питнаь про те, як керувати їх общиною і державою.
Рустемідська держава на початку її існування в другій половині VІІІ ст. Правління Абд ар-Рахмана блуло золотим віком ібадитів. Він був справедливим, розумним і кмітливим. Багато областей імама Рустемідів страждали від нападів кочівників і напівкочівників, що і вплинула на масове переселення арабських кочових племен в Пн. Африку в ХІ ст. Ібадитський імамат мав багато міжнародних зв’язків і в Тахарті почали прибувати посольства. Відновились торгові зв’язки з Суданом і з заходом Пн. Африки із Сходом. Купці усіх країн приїжджали в Тахарт і вели там торгівлю [30; 194].
В ібадитській общині велике значення надавалося розподіленню згідно з демократичними ідеями, серед бідних розподілялися предмети харчування і одяг, що дозволяло підтримувати рівень їх благоустрою і тим самим – послаблювати протиріччя між багатими і бідними станами суспільства. Існувало організоване оподаткування і апарат управління, судді (хади). Їх діяльність зосереджувалась головним чином на громадських справах, передусім пов’язаних з конфліктами в торгівлі. У сферу діяльності суддів не входили відносини між племенами, так як в цьому випадку конфлікти вирішувалися самими племенами.
Поява інституту поліції (асхаб алі-гмурта) було ознакою появи держави. Начальники чи офіцери поліції – асхаб амшурта здійснювали керівництво поліцейськими діями. Поряд з офіцерами поліції названі люди, що оточували їх чи здійснювали разом з ними обходи (таіфуна бікі). Не виключено, що це були добровольці [30; 195].