Musa b. Nusayr, Kuzey Afrika’nın fethinden sonra sıranın İspanya’ya geldiğini düşünmeye başlamıştı. Çünkü Müslümanlar için İspanya’dan başka gidilecek elverişli bir bölge bulunmamaktaydı. İspanya’nın o an içinde bulunduğu otorite boşluğu ve kargaşa ortamı da Müslümanların lehine olabilecek bir durum arz etmekteydi. Ayrıca Kral Witiza’nın oğulları ve Septe hâkimi Julianus da rivayete göre kendisini fetih için İspanya’ya çağırmaktaydı. Sonunda Musa b. Nusayr, Emevî Halifesi Velid b. Abdülmelik’e mektup yazarak, İspanya’yı fethetmek için izin istedi. Halife de ona yazdığı mektupta Müslümanların canını tehlikeye atmamasını, bütün orduyla İspanya’ya gitmektense küçük birlikler yollayarak durumu tetkik etmesini ve ondan sonra kararını vermesini istedi. Bunun üzerine Musa, Berberî asıllı olduğu ifade edilen Tarîf b. Mâlik komutasında 500 kişilik bir keşif birliğini İspanya’ya yolladı. İspanya’nın güneyinde Yeşil Ada’ya (Ceziretü’l-Hadra) Temmuz 710’da çıkan bu birlik durumun fetih için gayet müsait olduğunu gördü ve geri döndükten sonra izlenimleri hakkında Musa b. Nusayr’a bilgi verdi.