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