فلما رأى ذلك الناس أسرعوا إلى الدخول، فدعا موسى مولىً له كان على مقدماته يسمى طارق بن زياد، قيل هو فارسي وقيل هو من الصدف وقيل ليس بمولى، وقيل هو بربري من نفزه، فعقد له وبعثه في سبعة آلاف من البربر والموالى، ليس فيهم عربي إلا القليل. فهيأ له يليان المراكب وحل بجبل طارق يوم سبت في شعبان من سنة٩٢، وهو من شهور العجم شهر أغشت، وقيل في رجب من السنة، في اثنى عشر ألفاً غير ستة عشر رجلاً لم يكن فيهم من العرب إلا القليل.
وأصاب طارق عجوزاً من أهل الجزيرة فقالت له: كان لي زوج عالم بالحدثان، وكان يحدث عن أميرٍ يدخل بلدنا هذا ويصفه ضخم الهامة وأنت كذلك! ومنها أن بكتفه الأيسر شامةً عليها شعر، فإن كانت بك هذه الشامة فأنت هو، فكشف طارق ثوبه فإذا بالشامة على كتفه كما ذكرت العجوز، فاستبشر بذلك هو ومن معه.
وذكر عن طارق أنه كان نائماً في المركب فرأى في منامه النبي " - صلى الله عليه وسلم - " والخلفاء الأربعة يمشون على الماء حتى مروا به، فبشره النبي " - صلى الله عليه وسلم - " بالفتح وأمره بالرفق على المسلمين والوفاء بالعهد؛ وفي حكايةٍ إنه لما ركب البحر غلبته عيناه فرأى النبي " - صلى الله عليه وسلم - " وحوله المهاجرون والأنصار قد تقلدوا السيوف، وتنكبوا القسى، فيقول له النبي: يا طارق تقدم لشأنك! ونظر إليه وإلى أصحابه قد دخلوا الأندلس قدامه فهب من نومه مستبشراً وبشر أصحابه ولم يشك في الظفر، فنزل بالجبل شاناً للغارات في البسائط، ولذريق يومئذٍ غائب في غزاةٍ له، واتصل به الخبر فعظم عليه أمره، وفهم الخبر الذي أتى منه مع يليان، وأقبل مبادراً في جموعه حتى احتل بقرطبة أياماً والجنود تتوافى عليه،