الموحدين فسير عبد المؤمن معه جيشاً بقيادة براز بن محمد المسوفي، في شعبان 541هـ، ثم أمده بجيش آخر بقيادة موسى بن سعيد وجيش آخر بقيادة عمر بن صالح الصنهاجي. فلما عبروا الزقاق ونزلوا بالأندلس، هاجموا أبا القمر بن عزوز بشريش ورندة، فدخل في طاعة الموحدين، ثم قصدوا لبلة وأخضعوا يوسف بن أحمد البطروجي، ثم مضوا إلى مرتلة، فدخلوها وافتتحوا بعد ذلك شلب، وقصدوا باجة وبطليوس، فدخل أبو محمد سدراي ابن وزير في طاعتهم، كما انضوت اشبيلية في سنة 541هـ تحت لوائهم بعد ان اقتحموها براً وبحراً، ثم دخلوا مالقة في هذه السنة. غير أن يوسف البطروجي لم يلبث ان نكث بطاعته للموحدين، وحول الدعوة عنهم، كما ارتد عن طاعتهم ابن قيس في شلب، وعلي بن عيسى بن ميمون في قادس، ومحمد بن علي بن الحجام في بطليوس، بينما بقى أبو القمر بن عزوز على طاعتهم في شريش ورندة.

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