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