ولما عاد عبد المؤمن الى المشرق وفتح المهدية أحضر أمراء العرب واحلفهم في مصحف عثمان (رض) على السمع والطاعة والسير معه للجهاد بالاندلس. واستصحب منهم في عوده فلما قرب من وهران طلبه عرب افريقية في الرجوع الى حللهم. فاسعفهم. ونقل منهم الى المغرب الفا من كل قبيلة بعيالاتهم. وكانت نيته اخلاء افريقية من العرب ونقلهم الى المغرب والاندلس ليبعدهم عن الصحراء ويقربهم من عاصمته ويشغلهم بالجهاد.
وفي سنة ٥٨ خرج عبد المؤمن من مراكش يريد الجواز الى الاندلس. فندب عرب بجاية الى الجهاد برسالة ختمها بأبيات من نظمه وهي:
أقيموا الى العلياء هوج الرواحل ... وقودوا الى الهيجاء جرد الصواهل
وقوموا لنصر الدين قومة ثائر ... وشدوا على الاعداء شدة صائل
فما العز الا ظهر أجرد سابح ... يفوت الصبا في شدة المتواصل
وابيض ما ثاور كان فرنده ... على الماء منسوج وليس بسائل
بني العم من عليا هلال بن عامر ... وما جمعت من باسل وابن باسل
تعالوا فقد شدت الى الغزو نية ... عواقبها منصورة بالاوائل
هي الغزوة الغراء والموعد الذي ... تنجز من بعد المدى المتطاول
بها يفتح الدنيا بها يبلغ المنى ... بها ينصف التحقيق من كل باطل
أهبنا بكم للخير والله حسبنا ... وحسبكم والله أعدل عادل
فما هبنا الاصلاح جميعكم ... وتسريحكم في ظل أخضر هاطل
وتسويغكم نعمى ترف ظلالها ... عليكم بخير عاجل غير آجل
فلا تتوانوا فالبدار عنيمة ... وللمدلج الساري صفاء المناهل
قال صاحب المعجب: "فاستجاب له منهم جمع ضخم فانزل بعضهم نواحي قرطبة وبعضهم نواحي أشبيلية. وأقاموا هنالك.