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