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