على رسوم المهدي وتعاليمه ونظام حكومته باعتبارها نظماً رجعية لا تتفق مع روح الدين الصحيح، فسرت روح السخط بين القبائل، وأخذ الزعماء المتوثبون الذين يرقبون الفرص. وبينما كان المغرب يضطرم بعوامل الثورة على هذا النحو، والمأمون يشغل بقمع الخوارج عليه، كان سلطان الموحِّدين بالأندلس يضطرب في الوقت نفسه، ويتداعى وينهار حكمهم تباعاً.
ففي تلك الآونة، ظهر ابن هود يدعو إلى دعوة جديدة، تمثل فيها روح الأندلس الحقيقية، وهي: وجوب العمل على تحرير الأندلس من نير الموحِّدين والنصارى معاً. وكان المأمون حينما اشتد عليه الأمر بالأندلس، قد تحالف مع ملك قشتالة، وتنازل له عن عدد من القواعد والحصون، وتعهد بأن يمنح النصارى في أراضيه امتيازات خاصة، وذلك لقاء معاونة ملك قشتالة له على محاربة خصومه. وكان تحالف الموحِّدين مع النصارى على هذا النحو، يسبغ على دعوة ابن هود قوة خاصة، ويدفع الأندلسيين إلى الإنضواء تحت لوائه، وظهر ابن هود لأول مرة في أحواز مرسية في سنة (625 هـ - 1228 م) في الوقت الذي أخذ فيه سلطان الموحّدين يضطرب ويتصدع في الثغور والنواحي، ثم أغار على مرسية في عصبته القليلة، واستطاع أن ينتزعها من حاكمها السيد أبي العباس. وأخذ نجمه يتألق من ذلك الحين، فأعلن أنه يعتزم تحرير الأندلس من الموحدين والنصارى معاً، والعمل على إحياء الشريعة وسننها، ودعا للخلافة العباسية، وكاتب الخليفة المستنصر العباسي ببغداد، فبعث إليه بالخلع والمراسيم، وتلقّب بالمتوكل على الله. ولم يمض سوى قليل، حتى دخلت في طاعته عدة من قواعد الأندلس، منها جيان وقرطبة وماردة وبطليوس، ثم استطاع أن ينتزع غرناطة قصبة الأندلس الجنوبية من المأمون في سنة (628 هـ - 1231 م).
وفي العام التالي (629 هـ) توفى المأمون ملك الموحدين، وهو في طريقه إلى مراكش، ليعمل على إنقاذ عرشه من المتغلِّبين عليه. وبينما كان سلطان الموحدين بالأندلس يدنو سراعاً من نهايته، كانت دولتهم بالمغرب تدخل في