كانت بِدايَة فَتْح الأَندَلُس بأن يُولْيان حاكِم الجَزيرَة الخَضْراء غَضِبَ مِن لُذْريق (رُودْريغُو) مَلِك الأَندَلُس فاتَّفَق مع موسى بن نُصَير على أن يَدُلَّه على عَوْراتِهم ويُدْخِلَه الأَندَلُس, فكَتَب موسى إلى الوَليد يَسْتَأْذِنُه في غَزْو الأَندَلُس, فكَتَب إليه الوَليدُ: خُضْها بِالسَّرايا، ولا تُغَرِّر بالمسلمين في بِحْرٍ شَديدِ الأَهوال. فكَتَب إليه موسى: إنَّه ليس بِبَحْرٍ مُتَّسِع، وإنَّما هو خَليجٌ يَبِينُ ما وَراءَه. فكَتَب إليه الوَليدُ: أن اخْتَبِرْها بالسَّرايا، وإن كان الأَمْرُ على ما حَكَيْتَ. فبَعَث موسى رَجُلًا مِن مَوالِيه يُقالُ له طَريف بن مالِك أبو زُرْعَة في أربعمائة رَجُل ومعهم مائة فَرَسٍ، وهو أوَّلُ مَن دَخَل الأَندَلُس مِن المسلمين، فسار في أربع سَفائِن، فخَرَج في جَزيرَة بالأَندَلُس، سُمِّيَت جَزيرَة طَريف لِنُزولِه فيها، ثمَّ أَغارَ على الجَزيرَة الخَضْراء، فأَصابَ غَنيمَةً كَثيرَة، ورَجَع سالمَّا. فلمَّا رأى النَّاسُ ذلك تَسَرَّعوا إلى الغَزْو.