تحول شكهم به إلى يقين فقتلوه. فتركه ونوجه إلى سجلماسة فأقام بها - والجواسيس - العيون يطاردونه. وكان حاكم سجلماسة رجلا يعرف باسم - اليسع بن مدرار - فأهدى له أبو عبيد الله الهدايا وواصله، فقربه البسع وأحبه. فأتاه کتاب زيادة الله يعرفه أنه الرجل الذي يدعو إليه أبو عبد الله الشيعي، فقبض عليه وسجنه.

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