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