وبعد أن عبوا من العلم الصافي واخذوا ما شاء الله لهم من العلم خرجوا من السرداب في عام 140 للهجرة ، وعادوا إلى المغرب ومعهم أبو الخطاب المعافري وقد أوعز إليهم الإمام أبو عبيدة أن يبايعوه إماما عليهم حين تسنح لهم الفرصة ، ومما يدل على خروجهم من عند أبي عبيدة وقد تبحروا في العلوم قصة تروى عن أحدهم وهو إسماعيل ابن درار الغدامسي مع إمامه أبي عبيدة كما ذكرها الدرجيني في الطبقات ص 211 : ( ... فلما أرادوا الخروج من عنده هيأ الشيخ المركوب لتوديعهم ، ووضع رجله في الركاب - أي إسماعيل الغدامسي وضع رجله في الركاب - فسأله إسماعيل عن ثلاثمائة مسألة من مسائل الأحكام قبل أن يستوي على متن الدابة ، فقال له أبو عبيدة: أتريد أن تكون قاضيا يا ابن درار ؟ قال له : أرأيت إن ابتليت بذلك ! فبماذا تأمرني يرحمك الله ؟ .... ) .

انطلقوا ميممين شطر المغرب لإقامة شرع الله ، وبعد أن انهوا خمس سنوات مع إمامهم عادوا إلي المغرب تسبقهم أشواقهم لإقامة شرع الله وإحياء سنة رسول الله ، هذا وقد وضعوا الخطط السياسية المحكمة ، واعدوا القبائل البربرية لتستعد للثورة وتعلن الإمامة ، وهيئوا العدة العسكرية والبشرية لإنجاح هذه الثورة ، ولما وصلوا إلي المغرب ، فلما أحسوا أن الفرصة قد واتتهم وريحهم قد هبت بادروا بمبايعة أبي الخطاب عبد الأعلى المعافري ، حيث أن الإمام أبا عبيدة أوعز إليهم بذلك وأمرهم بقتله إن رفض ، وهذا يذكرنا بما حدث من الإمام السالمي رحمه الله عند رفض الإمام سالم بن راشد الخروصي رحمه الله قبول البيعة فأمر الإمام السالمي أبا زيد الريامي بضرب عنق الإمام سالم مما اضطر الإمام سالم إلى أن يقبل البيعة وهو يبكي رحمه الله ، ولما سئل الإمام السالمي عن الدليل الذي استند إليه في ذلك اخبرهم بما ورد عن الإمام أبي عبيدة من أمره طلابه بقتل أبي الخطاب إن رفض البيعة لما في ذلك من مفسده لأمر المسلمين .

هنا لم يجد أبو الخطاب مفرا من قبول البيعة ، وتمت البيعة له وكان ذلك في عام140 للهجرة ، وكانت المغرب في تلك الفترة واقعة تحت نير الدولة العباسية ، وبعد أن استمرت إمامة أبي الخطاب أربع سنوات ذاق فيها المسلمون طعم الأمان والعدل وإقامة شرع الله ولكن ما لبثت جيوش أبي جعفر المنصور أن وصلت إلى إفريقية بقيادة محمد بن الأشعث الخزاعي ، ولم يجد أبو الخطاب عناء في صد هذا الجيش العباسي ورده مهزوما ، ولكن ما لبث أن أعاد الكرة بجيش قوامه أربعون ألفا ، واستطاع أبو الخطاب التغلب عليه بفضل الله مرة ثانية وصدق الله حين قال : (( .... كم من فئة قليلة غلبت فئة كثيرة بإذن الله والله مع الصابرين )) البقرة : 249 .

وهنا لجأ ابن الأشعث إلى الحيلة والخيانة ، وهذا ديدنهم فهو ليس بغريب على أمثالهم ، وليس بعيد عنا ما حدث للتابعي الجليل أبي بلال مرداس بن حدير التميمي وأصحابه الأربعين من بني أمية وقائدهم ابن زرعه الذي انهزم أمام أربعين رجلا بالرغم من أنه على رأس ألف جندي وكان حريا به أن ينهزم ، فان أبا بلال وأصحابه الأربعين الرجل فيهم عن ألف رجل ، فبعث بنو أمية إليه بقائد جديد وهو عباد بن اخضر على رأس أربعة آلاف جندي فلم يتغلب على أبي بلال وأصحابه مما اضطره إلى اللجوء إلى الخيانة فهجم على أبى بلال وأصحابه وهم يؤدون صلاة الجمعة فخان العهد حيث انهما اتفقا على وقف القتال إلى حين أن ينتهي الجميع من أداء صلاة الجمعة فأين هي عهود المسلمين ، وهنيئا لتلك الأجساد الطاهرة الجنة التي استشهدت خاشعة بين يدي رب العزة والجلال .

وهذا ما حدث كذلك للإمام الجلندى بن مسعود رحمه الله وأصحابه حين هجم عليهم الجيش العباسي بقيادة خازم بن خزيمة فقاتلوهم ولم يتمكنوا منهم ، فلجأ خازم بن خزيمة إلى الغدر والمكيدة ، فأمر بإحراق بيوت الجلندى وأصحابه وكان بها الأطفال والنساء والشيوخ فأي دين هذا الذي يأمر بقتل الأطفال والنساء والشيوخ؟! وما الفرق بين هؤلاء وبين ما يفعله اليهود في فلسطين وما تفعله الدول الغربية في العراق وما يفعله الصرب في مسلمي البلقان .

إذا فالغدر ديدنهم فهم لا يقوون على المواجهة رجلا لرجل ، نعم لجأ ابن الأشعث إلى الغدر حين علم ألا طاقة له بالتغلب على هذه الثلة المؤمنة إلا بالخيانة فتظاهر بالانسحاب إلى المشرق ، وتفرق جيش أبي الخطاب الذي كان من الأهالي والفلاحين الذين عادوا إلى مزارعهم في موسم الحصاد ، مما سهل على ابن الأشعث القضاء على من بقي مع أبي الخطاب فقتلهم جميعا والله المستعان على ذلك وعند الله تجتمع الخصوم.

في تلك الأثناء كان عبد الرحمن بن رستم واليا على القيروان من طرف الإمام أبي الخطاب ، وكان في طريقه لنصرة الإمام ولكنه علم بموت الإمام مما اضطره للفرار إلى المغرب الأوسط بصحبة ابنه عبد الوهاب وخادمه ،وظل سائرا بين القبائل الاباضية متخفيا سالكا طريقا وعرة من جنوب الجزائر وقطعها من شرقها إلى غربها إلى حين وصوله إلى جبل يدعى سوفجج ، وقد وجد إمامنا المنتظر أنصارا له في الطريق ساروا معه إلى الموقع المذكور ، ولحق به ابن الأشعث وظل يحاصر الجبل المنيع إلى أن يأس من اقتحامه فرجع جارا أذيال الهزيمة . وظل عبد الرحمن هنالك بين أنصاره من القبائل البربرية حتى إذا اجتمع حوله من أهل العلم والصلاح من يثق بهم ، ووجد نفسه قادرا على الشروع في بناء دولته اتجه نحو موقع ( تيهرت ) وشرع في بناء دولته الشامخة في نهاية 155 للهجرة وبداية 156 للهجرة .

اجتهد إمامنا المرتقب ومن معه على إيجاد مكان مناسب لبناء مدينة مثالية تحصنا ومنعة وهواء وجمالا وكان الموقع المختار أشجارا وأحراشا ومرتعا لأنواع السباع والوحوش .

ويروى أن عبد الرحمن وأصحابه لما اعتزموا بناء مدينة تيهرت بهذا المكان المغطى بغابة كثيفة كانت مأوى للوحوش ، كلف أحدهم بان ينادي بأعلى صوته ثلاث مرات في ثلاثة أيام : أيتها الوحوش إنا نريد أن نعمر هذا المكان فمن يريد السلامة فليخرج منه ، وعلى إثر هذا النداء شاهدوا السباع والوحش تحمل أشبالها في أفواهها خارجة من الغابة. وهذا ليس بغريب على من آمن بالله حق الإيمان واتبع منهج الرسول صلى الله عليه وسلم وأصحابه الأخيار ، فقد وقع مثل هذا للصحابة والتابعين عندما أرادوا تأسيس مدينة القيروان كما هو معلوم.