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