في سيره وئيداً، واحتفل في الطريق بعيد الأضحى، وقدم ولده السيد أبا يوسف يعقوب على مقدمة الجيش، فسبقه إلى تلمسان. ووصل الخليفة في قواته إلى تلمسان في أوائل سنة ٥٧٦ هـ، ولما كملت أهبة الجيش وتعبئته، خرج من تلمسان في الثاني عشر من شهر صفر، متجهاً إلى إفريقية، فلما وصل إلى بجاية نزل بها. وتحقق لديه أن القائد علي بن المنتصر متواطىء مع قريبه الثائر بقفصة، وأنه يوالي تحريضه على الاستمرار في الثورة، ويوالي تحريض العرب لتأييده، وضبطت بمنزله رسائل تؤيد ذلك، فقبض عليه، وأحيط بسائر أمواله. ثم سار الخليفة من بجاية، فلما قرب من قفصة، بادر أشياخ العرب من رياح إلى المثول لديه، وتأكيد ولائهم وطاعتهم. وضرب الخليفة الحصار حول قفصة وضربها بالمجانيق، حتى اضطر علي بن الرند إلى الإذعان والتسليم، أو التوحيد وفقاً لقول البيذق، ثم ارتد إلى تونس وفقاً لرواية أخرى، واحتل الموحدون قفصة وذلك في رمضان سنة ٥٧٦ هـ (فبراير ١١٨١ م) وعقد الخليفة بولاية إفريقية والزاب لأخيه السيد على أبي الحسين، وبولاية بجاية أو ولاية القيروان على قول آخر لأخيه السيد أبي موسى (١).
وانتهز الخليفة هذه الفرصة لتجديد مساعيه في استمالة العرب الذين ينزلون بهذه الأنحاء من إفريقية وترغيبهم في الجهاد بالأندلس. وقد شرح لنا هذه المساعي في رسالة الفتح التي وجهها إلى الموحدين بقرطبة. وذلك أنه لما اجتمع لديه أشياخ قبائل رياح وكبراؤهم من جميع الأنحاء، ذُكّروا بما كان لأسلافهم من فضل سابغ في نصرة الدين، وأنه يجدر بهم أن يحذوا حذو أسلافهم في الاضطلاع بتلك المهمة الجليلة، وأن خير ما يصنعونه في ذلك هو المساهمة في الجهاد بالأندلس، وغزو النصارى بها، سيما وقد تفاقم عدوانهم في الآونة الأخيرة، وأن أولئك الأشياخ أبدوا أنهم على أتم أهبة للاستجابة إلى هذه الدعوة، وأن قبائل رياح كلها، وبطونها وأفخاذها، أبدوا جميعاً أنهم يقبلونها بقلوب خالصة، ونيات صافية، وأنهم أخذوا بالفعل في الحركة والاحتشاد، كل طائفة صوب الطريق التي تفضلها وتراها أيسر لمجازها، وتوالت جموعهم حتى امتلأت بها تلك البطاح والسهول. وكان ممن حضر ذلك الجمع الشيخ أبو سرحان مسعود بن سلطان بن زمام، فلما وقع العزم على الاستجابة، أخذ في الرحيل بأهله وولده وكل من تبعه من
(١) البيان المغرب القسم الثالث ص ١١٤، وابن خلدون ج ٦ ص ٢٤٠ و ٢٤١، وكتاب أخبار المهدي ابن تومرت ص ١٢٥، والمعجب للمراكشي ص ١٤١، و ١٤٢.