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