وكانت نهايته في سنة (144 هـ) حين التقى مع قائد الحملة العباسية محمد بن الأشعث في"تورغا"- على مسيرة ثمانية أيام من طرابلس -، فأبادهم جميعًا هذا القائد العباسي، وكانت عدتهم أربعة عشر ألفًا، واحتزّ محمد بن الأشعث رأس أبي الخطاب، وبعث به إلى الخليفة العباسي المنصور في بغداد.

وكان أبو الخطاب قد ولّى عامله عبدالرحمن بن رستم على مدينة القيروان، فلما حصل له ما حصل؛ فرّ عبدالرحمن بن رستم من القيروان، وأخلاها لابن الأشعث، وتوجّه إلى المغرب حيث اعتصم بجبل منيع هناك، وحاصره فيه ابن الأشعث مدة فلم يتمكن منه، فارتحل عنه. ثم إن ابن رستم استطاع أن يجمع فلول الإباضية هناك، ويقيم دولة في مدينة"تيهرت"- شمال الجزائر الآن -، عرفت هذه الدولة بـ"الدولة الرستمية"نسبة إلى عبدالرحمن بن رستم هذا، وهو ابن رستم بن بهرام بن سام بن كسرى أنو شروان ملك الفرس، وذلك في سنة (160 هـ) .

وكانت وفاة عبدالرحمن بن رستم هذا سنة (171 هـ) .

ثم تولى بعده ابنه عبدالوهاب، وتوفي سنة (190 هـ) .

ثم تولى بعده ابنه أفلح بن عبدالوهاب، وتوفي سنة (240 هـ) .

ثم تولى بعده ابنه أبو بكر بن أفلح، فلم تدم خلافته إلا نحو عام، قيل: إنه مات بعدها، وقيل سلّم الأمر لأخيه أبي اليقظان محمد بن أفلح سنة (241 هـ) ، واستمرت خلافته إلى وفاته سنة (281 هـ) .

ثم تولى بعده ابنه أبو حاتم يوسف بن أبي اليقظان الذي مات مقتولًا من بعض قرابته سنة (294 هـ) .

ثم تولى بعده أخوه اليقظان بن أبي اليقظان الذي نصّبه قرابته الذين قتلوا أخاه، وهو آخر من تولى من بني رستم، حيث انتهت دولتهم على يد أبي عبدالله الشيعي داعية العبيديين، وذلك في سنة (296 هـ) .