В 758г. Имам (ибадиййа) Магриба Абу-л-Хаттаб назначил Абд ар-Рахмана ибн Рустама, одного из «Носителей знания» (Хамалат аль Ильм), своим наместником в Кайруане.
В 761г. Кайруан, завоеванный наместником Египта ибн ал-Ашасом, переходит под власть Аббасидов. Абд ар-Рахман отступил в Средний Магриб (Алжир), где продолжает руководить племенами амазигов, признававших его авторитет, в качестве наместника правителя. Чтобы быть равноудаленными от местных племен и не вызывать конфликтов по поводу месторасположения ставки, Абд - ар Рахман сделал своей столицей заброшенную римскую крепость (лагерь легиона) Тахарт (римский - Тиарет в настоящее время - Тагдемт), расположенный на склоне Джебель-Джоззуля, возвышавшийся на тысячу метров над степными пастбищами. Отсюда он смог заново на короткое время (772 год ) утвердиться в Кайруане.
Абд ар-Рахман ибн Ростем стал губернатором нового имама ал-ибадиййа в Магрибе Абу Хатима аль-Малзузи. Спустя несколько месяцев после его гибели, ибн Ростем оставил Кайруан и отступил в свою резиденцию – Тахерт, продолжал осуществлять руководство над большей частью племен Среднего Магриба (Алжир), тогда как в Ифрикии и Кайруане утвердились Аббасиды в лице их амира Мухаллабида Хатима аль Азди, который основал местную династию аббасидских наместников, вернув на время "величие и славу" потомкам Мухаллаба ибн Ас-Суфры, раннее в Омеййадскую эпоху бывших друзьями и союзниками ибадитов.
В 777г. Абд ар-Рахман после 5 лет успешного противостояния с правителями Кайруана и Триполи смог обеспечить безопасное существование своего государства, расширив его пределы. В частности, он отвоевал у Мухаллабидов побережье. Были открыты и отстроены порты, через которые наладились тесные торговые и политические контакты с Омейядами из аль-Андалуза. Тогда же и был провозглашен «имамат зухур» («свобдного исповедания веры»), а Абд ар-Рахман, до этого возглавлявший «совет шейхов» , был избран имамом.
Избранию ибн Ростема кроме его личных достоинств и качеств способствовало и то обстоятельство, что он не относился ни к одной из влиятельных фракций, не только не будучи членом племен амазигов (берберов), но и арабом, которые среди ибадитов Магриба были в большинстве представителями хадрами (народа Хадрамаута), в то время как новый имам был персом.
С согласия совета улама и шейхов племен должность имама была закреплена за представителями семьи ("Дома") Абд ар Рахмана. Они сочли такую практику оправданной, чтобы избежать конкуренции между представителями местных колен и кланов амазигов (берберов) в их возможной борьбе за имамат. При этом сама процедура выборов имама не отменялась, но претенденты на избрание ограничивались членами семьи Абд ар-Рахмана.
Так было основан Имамат Рустамидов.
Имам Абд ар Рахман в ходе своего правления установил мирные отношения со всеми соседями, что способствовало процветанию имамата. Так, в следующие годы Тахарт стал быстро заселяться. Причем переселенцы прибывали сюда из самых отдаленных областей исламского мира, привлеченные как изобилием плодородных земель, так и слухами о справедливом государственном устройстве. Вскоре все окрестные земли были орошены и стали обрабатываться, а сам город превратился в ключевой центр африканской и, прежде всего, транс сахарской торговли. Сюда кочевники пригоняли в летнее время стада и обменивали продукты скотоводства на зерно у жителей Телля. По прибытии вожди [племен] встречались с именитыми гражданами, затем возвращались в свои кочевья. «Не было чужеземца, — пишет суннитский ученый Ибн Сагир, который длительное время проживал s Тахерте — который, посетив город, не обосновывался бы в нем и не строил бы себе там жилье, будучи прельщен царящим изобилием, праведным поведением имама, его справедливостью по отношению к народу и безопасностью, какою пользовались все жители и их имущество. Вскоре о каждом доме в городе говорили: этот дом принадлежит такому-то из Куфы, этот — такому-то из Басры или из Кайруана; вот мечеть пришедших из Кайруана и их базар; вот мечеть и базар пришельцев из Басры или из Куфы».
В конце жизни Абд ар-Рахмана делегация ибадитов Басры, посетивших город, отмечала в своем донесении, что Тахарт изменился во всех отношениях — здесь появились дворцы, плодовые сады, мельницы, хорошо экипированная конница, большое количество рабов , но сам имам Абд ар-Рахман продолжал вести аскетичный образ жизни.
Так, — согласно Ибн Сагиру — Ибн Ростем, занятый заделыванием щелей на своей террасе, сначала закончил работу и только потом слез с лестницы, чтобы принять ибадитских посланцев из Ирака. Он предложил им лепешки с жиром и топленое масло. В комнате была только подушка, на которой он спал, его сабля и пика, а в другой части дома был привязан его конь. Он отослал обратно второе посольство (из Ирака), вернув им подарки, говоря, что его община не столь бедна, чтобы принимать дары.
Имам Абд ар-Рахман умер в 787 (171 ) году.
Утверждение нового имама, вопреки согласованной прежде позиции о принадлежности имамата к семье Абд ар Рахмана ибн Ростема, встретило противодействие некоторых племен амазигов. Ряд берберийских кланов не согласились признать выборы имама, которым стал сын Абд ар-Рахмана — Абд ал-Ваххаб б. Абд ар-Рахман. По мнению их вождей, сами выборы были пустой формальностью, с учетом того, что никакой иной кандидатуры кроме Абд ал-Ваххаба не рассматривалось. Шейхи амазигов, таким образом, сочли данный акт, противоречащим шариату. При этом, они не считали себя нарушителями договора относительно раннее данного согласия на выбор имама из числа членов семьи Ибн Рустама, так как, они полагали, что выборов не было в принципе.
Абд ал-Ваххаб вынужден был пойти навстречу требованиям берберийских шейхов и согласился созвать Совет для новых выборов имама. Целый месяц длился спор по поводу двух кандидатов: Абд ал-Ваххаба ибн Абд ар-Рахмана и Масуда ал-Андалуси. В конце концов, лидеры ибадитов подтвердили правомочность правления Абд-ал-Ваххаба простым голосованием, - отдав за него большинство голосов. Однако, один из вождей амазигов - Йазид бин Фандин, принадлежавший к отдельной группе ибадитов – аль-нуккар, к которой относились, прежде всего, племена раннее исповедовавшие софризм, чьи взгляды в большей степени совпадали с нуккаритами, чем с ортодоксальными ибадитами – аль-вахбийа (сторонники строгого следования принципам первого имама мухаккимитов ибн Вахба ар Расиби, отсюда и название и людей Ан-Нахраван) , несмотря на все доводы, отказался признать эти выборы и со своими людьми пытался ворваться в дом имама и сместить его силой, но нападение было отражено, а Йазид ибн Фандин погиб в схватке. После этого и до конца имамата Абд ал Ваххаба страна под его руководством продолжала развиваться и процветать.
В 812 г. Триполитанские ибадиты из племен Нафуса, входившие в сотав имамата попытались овладеть Триполи, некоторое время осаждали город, но не смоги его взять. Но после смерти Ибрахима I — основателя тунисской династии Аглабидов, признававшей авторитет Аббасидов — Триполи добровольно признал власть Рустамидов, а представители племени Нафуса стали его губернаторами. Это послужило укреплению авторитета Рустамидов в областях между Тахартом и Триполи, особенно в Джериде и части Заба, которые также вошли в состав Рустамидского государства. Таким образом, столица Аглабидов Кайруан и, принадлежавший им Тунис, были окружены со всех сторон территорией ибадитов.
Абд ал-Ваххаб еще при жизни передал многие государственные дела в ведение своего сына Афлаха, который своей исполнительностью и справедливостью заслужил уважение представителей племен и улама и был избран имамом в 823 г.
Во времена Афлаха ибадиты начинают осваивать территорию к югу от Сахары - Биляд ас Судан (прежде всего современные Нигер и Мали), с народами которого они наладили торговые связи. Теперь же дело дошло до образования постоянных поселений и городов, таких как Гао и Дженне, которые посещали и где проживали, в том числе и члены правящего дома Рустамидов. Кроме того, многие правители местных народов и многие жители этих мест были обращены в ислам.
При имаме Афлахе началась новая война с Аглабидами, чей правитель Абу – ль Аббас смог отвоевать у ибадитов некоторые области Среднего Магриба, где построил крепость аль-Аббасийа, названную в честь своих сюзеренов. Имам Афлах смог захватить и разрушить эту крепость, вернув потерянные территории. В этой связи стоит отметить, что это событие вызвало радость и в Кордове и Андалузе, где правили Омеййады, с которыми у Рустамидов сложились наиболее доверительные отношения. Узнав о взятии и сожжении Аббасии, Кордовский правитель направил имаму Афлаху 100 000 дирхемов, в качестве признания его заслуг в деле борьбы с ненавистными ему Аббасидами.
Еще раннее в 822 году (207) году эмир Кордобы Абд ар Рахман II устроил теплый прием трём сыновьям Абд ал-Ваххаба, которые возглавили посольство, чтобы приветствовать его приход к власти в Андалузе, где те проживали длительное время. Стоит отметить, что в 844 году (229) году Кордоба официально проинформировало Тахерт о победе, над вторгнувшимися в халифат викингами. Это было связано, в том числе, с тем, что многие видные представители семьи Рустамидов и племен амазигов, исповедующих ибадизм, занимали высокие должности в Кордове, включая военных амиров и визирей. Этот же период – господства Омеййадов в Андалузе, -был отмечен появлением многих книг, написанными ибади-учеными в этой стране, где они могли работать открыто, не опасаясь преследований ...
