ولما ضمن موسى ولاء أهل المغرب واستمساكهم بدعوة الإسلام، أخذ يعد العدة لغزو جديد، وبينما هو يفكر في هذا الأمر إذ جاءه رسول من قبل طارق بن زياد يخبره بأن يوليان حاكم (سبته) عرض عليه أن يتقدم لغزو أسبانيا، وأنه على استعداد لمعاونة العرب في ذلك، وتقديم السفن اللازمة لنقل الجنود المسلمين، وبعث موسى إلى الخليفة الوليد بن عبد الملك يستشيره، فردَّ عليه الخليفة بقوله: (خضها أولاً بالسرايا يعني بقلة من الجنود حتى ترى وتختبر شأنها ولا تغرر بالمسلمين في بحر شديد الأهوال) .
فأرسل موسى رجلاً من البربر يسمى (طريف بن مالك) في مائة فارس وأربعمائة رجل، وركب هو وجنوده البحر في أربعة مراكب حتى نزل ساحل الأندلس فأصاب سبيًا كثيرًا ومالاً وفيرًا، ثم رجع إلى المغرب غانمًا سالمًا، وفي شهر رجب من عام 92هـ جهز موسى جيشًا خليطًا من العرب والبربر تعداده سبعة آلاف جندي بقيادة طارق بن زياد، وانطلق طارق بالجيش إلى أن وصل سبتة، وهناك خطط لعبور المضيق، وفي اليوم الخامس من شهر رجب سنة 92هـ (إبريل 710م) وبفضل الله كانت آخر دفعة من الجنود بقيادة طارق تعبر المضيق الذي حمل اسم طارق بن زياد منذ ذلك الوقت.
ونزل طارق -قائد جيش موسى بن نصير- أرض الأندلس، وبعد عدة معارك فتح الجزيرة الخضراء، وعلم الإمبراطور (لذريق) بنزول المسلمين في أسبانيا من (بتشو) حاكم إحدى المقاطعات الجنوبية الذي بعث إليه يقول: أيها الملك، إنه قد نزل بأرضنا قوم لا ندري أمن السماء أم من الأرض، فالنجدة .. النجدة، والعودة على عجل.