وبعث موسى بن نصير إلى الخليفة الأموي الوليد بن عبدالملك يستأذنه في فتح هذه البلاد وواصفا له مكانتها من المسلمين مبينا سهولة دخولها بناء على ما أوضحه له يوليان، فأمره الوليد بن عبد الملك بإرسال سرية صغيرة تختبر تلك البلاد كي لا يقع المسلمين في مأزق في تلك البلاد، فأرس موسى بن نصير أحد قادة جنده ويسمى طريف بن ملوك فعبر إلى الأندلس في خمسمائة جندي وكان ذلك في رمضان سنة إحدى وتسعين للهجرة، ونزلوا في بلدة سميت باسم القائد طريف وشن المسلمون غارات على الساحل غنموا فيها مغانم كثيرة ثم رجعوا إلى موسى بن نصير بما حصلوا عليه في تلك المعارك.
بعدما رأى موسى بن نصير نتيجة السرية التي قام بها طريف بن ملوك أخذ يجهز جيشا كبيرا وندب على رأسه رجلا بربريا شجاعا يسمى طارق بن زياد، وأرسله إلى الأندلس على رأس سبعة آلاف مقاتل مسلم جلهم من البربر الذين حسن إسلامهم والبربر كانوا يتصفون بالقوة والشجاعة والإقدام، وبدأ عبور المسلمين إلى الأندلس ولم يكن لديهم سوى أربعة سفن فتم العبور على دفعات واختبأ الذين عبروا أولا حتى عبر الجيش كله وتجمعوا عند جبل سمى بجبل طارق تيمنا باسم القائد الفاتح طارق بن زياد، واستولى المسلمون على الجزيرة الخضراء قبالة جبل طارق فصارت مواصلات الجيش مع أفريقيا حيث المسلمون كلها آمنة.