ولم يكد عبد المؤمن يستحلق أولئك الأعراب بالجندية حتى بدأ يعلن عن مراده فيهم ونيته في توجيههم إلى القتال بالأندلس، وصار يبعث لمسلمي الجزيرة رسائل وقصائد يخبرهم فيها بما سيقوم به هؤلاء العرب من جهاد لأعداء الدين، ويطمئنهم على مصيرهم في تلك البلاد، وقد كانوا يومئذ في ضيق شديد من تكالب النصارى عليهم، فمن ذلك ما ورد في قصيدة بعث بها طي رسالة مؤرخة في ربيع الأول عام (٥٥٥ هـ - مارس ١١٦٠ م) من محلته المنصورة قرب مدينة قسنطينة إلى أهل الأندلس:
فيا معشر الأشياخ من كلّ طالب … ومن حافط للذكر ألفاظه سرد
نبشركم أنا اهتممنا بأمركم … فلبتكم منا المسومة المجرد
ويصحبنا من خالص العرب معشر … أنابوا فما ردوا وتابوا فما ارتدوا
رأوا في ذبوهم عبرة فتيقظوا … وكان لهم في غي غيرهم رشد
ستغزو بلاد الروم منهم عصائب .... ويحمي حمى التوحيد من خيلهم جند
فطوبى لأهل الغرب ما ذا يرونه … لقد جل قدرا أن يحيط به الحد
جيوش بنصر الله تهمي عليكم … يروق بها وهد ويزهي بها نجد
ويشجي بمرآها الأعادي كأنما … عليهم بها صم الشوامخ تنهد
ستعلم أرض الروم أي فوارس … على ظهرها منهم إذا وفد الوفد
وأي رجال للحروب إذا بدت … أسود شري بخشي ترابيها الأسد
وأنا وإياهم لحتم غلابنا … لهم وكلام الوحي ليس له رد
وبر عبد المؤمن بوعده لأهل الأندلس، فإنه لَمْ يمكث بالمغرب بعد رجوعه من إفريقيا إلَّا بقدر ما أعاد ترتيب الجيش وتسليحه، وهيأ ميرة أجناده وعلف دوابه، ثم عبر البحر إلى الأندلس في شهر نوفمبر (١١٦٠ م - ذو القعدة ٥٥٥ هـ) مصطحبا معه كتائب وفيرة العدد شديدة الشره إلى الحرب والقتال فلفت منظرهم وهم بحال من البداوة والفطرة، وبازياء حربية غريبة لَمْ تؤلف رؤيتها - أنظار النّاس، فأعجبوا بهم واستبشروا بمقدمهم، ونظم الشعراء في تمجيدهم والإشادة بشجاعتهم ونجدتهم، والتعبير عن الآمال المعلقة عليهم القصائد الغر الطوال.