كان فتح الأندلس نتيجة طبيعية لتمام فتح المغرب؛ لأن الأندلس هو الجناح الغربي للمغرب، ولأن الأندلس كان المجال الحيوي للفتح الإسلامي بعد إنجاز فتح المغرب الأفريقي واستقرار الفتح فيه بانتشار الإسلام، ولم تستعصي على موسى غير مدينة سبته لمناعتها ووصول الإمدادات إليها من أسبانيا القوطية عن طريق البحر، وكان يحكمها من قبل القواط في أسبانيا حاكم اسمه جوليان ويسميه المسلمون يليان أو إليان أو يوليان.

واختلف المؤرخون في نسب يوليان فقيل إنه قوطي، وقيل: إنه رومي، ورأي ثالث ينسبه إلى بربر غمارة.

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

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