On raconte que, durant le passage de Tanger vers l'Andalousie, Tariq Ibn Ziad s'étant endormi, le prophète Mohammed (PSL) lui apparut en songe. Autour du prophète étaient rangés El Mohadjirins et El Ansares. Ils tenaient une épée à la main ; des arcs étaient suspendus à leurs épaules. Le prophète s'approcha de Tariq, et lui dit: « Oh Tariq ! poursuis ton entreprise, sois fidèle à tes engagemens, et traite les Musulmans avec douceur. » En achevant ces mots, le prophète, suivi de ses compagnons, entra dans l'Andalousie. Aussitôt que Tariq fut réveillé, il communiqua cette vision à ses soldats. Ceux-ci furent transportés de joie, et ils regardèrent la vision de leur chef comme un présage certain de la victoire.

Une première flotte, composée de quatre vaisseaux, arriva bientôt au pied du mont Calpé , qui reçut alors le nom de Djabel Tariq ( Gibraltar). Tariq, ayant touché le sol de l'Andalousie, se mit en marche, résolu de vaincre ou de périr. Rodrigue ne tarda pas à être instruit de cet événement. « Un peuple étranger, lui dit-on, s'est montré dans l'Andalousie ; nous ignorons s'il descend du » ciel, ou s'il sort de la terre. »