Endülüs fatihi Tarık bin Ziyad, İspanya'ya çıkışında onikibin kişilik ordusuyla Kral Rodrik'in doksanbin kişilik ordusunu yenmişti (92/711 Mayıs). Daha sonra da Endülüs'te fetih hareketlerini sürdürmüştü. Tarık ve ordusu ülkenin başşehri olan Tuleytula üzerine yürüyünce, ahali korkudan kaçıp şehri boşaltmış, böylece orası hıristiyanlardan kolayca alınmıştı. Bu fetihten sonra Tarık, dağın arkasında 'Medinetü'l-Mâide' (Sofra Şehri) denilen yere geçti. Burada Hz. Süleyman a.s.'ın sofrasını ele geçirdi. Bu sofra yeşil zümrütten yapılmış, kenarları ve ayakları inci, mercan, yakut ve benzeri mücevherlerle süslüydü. Üçyüzaltmış ayağı vardı.

Kuzey Afrika valisi olan ve baştan beri Tarık'ın fetihlerine destek ve yardımda bulunan Musa b. Nusayr da, Tarık'tan bir yıl sonra  onsekizbin askerle, gördüğü lüzum üzerine  Endülüs'e girmiş; iki ayrı koldan fetihler sürerken, iki ordunun buluşması ancak bir yıl sonra mümkün olmuştu. Böylece iki büyük komutanın gayretiyle Endülüs fethi iki yılda tamamlanmıştı.

Endülüs'ün fethiyle ilgili, bazı garip olaylar da anlatılır. Şöyle ki, Tarık b. Ziyad Cebel-i Tarık Boğazı'nı geçip Endülüs'e girince, esirler arasında yaşlı bir kadın ona şöyle demiş:

- Böyle olayları iyi bilen bir kocam vardı. Buralara gelip galip olacak bir komutandan bahsedip dururdu. Bu komutanın sol omuzunda kıllı bir ben olduğunu söylerdi.

Tarık elbisesini kaldırınca, söylendiği gibi bir ben görüldü. Tarık ve yanındakiler bunu da bir fetih müjdesi saydılar.

Musa b. Nusayr şehirleri zaptederek İspanya içlerinde ilerlerken, birçok kalıntının da yer aldığı geniş bir araziye ulaşır. Orada dikili bir taş üzerinde oyma yazılarla şu yazıyı görür: 'Ey İsmailoğulları (Araplar)! Sizin varacağınız son yer burasıdır. Artık geri dönünüz. Niçin döneceğinizi de bildireyim: Sizler aranızda kavga ve ihtilafa düşeceksiniz.' Musa buradan geri döner.

Derler ki, Romalılar Endülüs'e girdikleri zaman bir evle karşılaştılar. Onlardan her kral buraya bir kilit ekliyordu. Gotlar da aynı şeyi yaptılar. Rodrik İspanya kralı olunca, bütün uyarılara rağmen bu kilitleri açtı. İçeride kırmızı sarıklı ve siyah atlı Arapların resmini gördü. Bir de şöyle bir yazı vardı: 'Bu ev açıldığında, bunlar da bu ülkeye girecekler.' İşte o sene Endülüs fethedildi.