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