عبرت الجيوش الإسلامية المجاز (مضيق جبل طارق) بقصد الجهاد سنة 479 هـ1، من سبتة إلى الجزيرة الخضراء تباعاًَ: فكان أوّلها قوةّ من الفرسان بقيادة داود بن عائشة، وآخرها موكب أمير المسلمين يوسف بن تاشفين، يوم الخميس منتصف ربيع الأول عام 479 هـ/30 حزيران 1086 م 2.
ويذكر أنّه خلال العبور هبّت ريح عاصف أثارت أمواجاً عالية، فرفع الأمير يوسف يديه إلى السّماء يدعو الله عز ّوجل:
"اللهم إن كنت تعلم أنّ في جوازنا هذا خيراً وصلاحاً للمسلمين فسهّل علينا جواز هذا البحر، وإن كان غير ذلك فصعّبه حتى لا أجوزه". واستجاب الله دعاءه، "فسهّل له المركب، وقرّب المطلب" 3. وما كاد يطأ بقدميه أرض الأندلس حتى سجد لله شكراً. وتلقّاه المعتمد بن عبّاد في وجوه من دولته، وقدّم إليه الهدايا والتّحف، وتسلّم الأمير قلعة الجزيرة الخضراء باحتفال حضره القضاة والفرسان والمعتمد، كما تسلّم عدّة قلاع وحصون أخرى، قام بإصلاحها، وأعاد تحصينها، أتمّ تحصين، ونظمها حسب رأيه وإستراتيجيته الخاصة، ورتب لها حامية مختارة من جنده لتسهر ِعليها، وشحنها بمقادير عظيمة من الأقوات، والذخائر، والمؤن، لكي تغدو ملاذاً أميناَ، يلتجيء إليه، إذا منيت الحملة بالفشل 4.
وفشا خبر عبور الأندلس فقوبل بالترحيب وانتعاش الآمال من قِبَل جميع المسلمين في الأندلس، وتحرّكت في نفوسهم روح الجهاد فتوافد إليه المتطوّعة من كلّ مكان، كما جاءته الوفود مرحّبة.