وكان قد تم له يومئذ فتح سبتة، فسار إليها، والجيوش تتلاحق في أثره من الصحراء، وبلاد الزاب، ومختلف نواحي المغرب، وأصلح مرافئها وحشد السفن لعبور قواته، وكان أول ما عبر منها قوة من الفرسان بقيادة داود بن عائشة، عبرت إلى ثغر الجزيرة الخضراء، واحتلته وفقاً لما تم الاتفاق عليه، ثم أخذت الجيوش المرابطية تعبر تباعاً، حتى تم عبورها جميعاً إلى شبه الجزيرة. وفي في يوم الخميس منتصف ربيع الأول سنة ٤٧٩ هـ (٣٠ يونيه ١٠٨٦ م) عبر البطل الشيخ في بقية قواته. وما كادت السفن العابرة تمخر عباب المضيق، حتى اضطرب البحر وتعالت الأمواج، فنهض الزعيم المرابطي حسبما يحدثنا بنفسه وسط سفينته، وبسط يديه بالدعاء نحو السماء قائلا:" اللهم إن كنت تعلم أن في جوازنا هذا خيرة للمسلمين، فسهل علينا جواز هذا البحر، وإن كان غير ذلك فصعبه حتى لا أجوزه ". ثم يقول لنا، إنه ما كاد يتم كلامه حتى " سهل الله المركب، وقرب المطلب ". وشاء ربك أن تعبر السفن المرابطية، في ريح طيبة وبحر هادىء، وأن تصل إلى ثغر الجزيرة في سلام (١).
(١) روض القرطاس ص ٩٣. وهذا ما ذكره يوسف بن تاشفين نفسه في خطابه بالفتح إلى المعز بن باديس. (ويراجع الخطاب المذكور في باب الوثائق في نهاية الكتاب).