جهز موسى بن نصير جيشًا من العرب والبربر يبلغ سبعة آلاف مقاتل، وأسند قيادته إلى طارق بن زياد لفتح الأندلس.
كان تجهيز هذا الجيش هو المفتتح لدخول الإسلام على يد موسى بن نصير إلى القارة الأوروبية، حسب تأكيد «محمد عبدالله عنان» فى الجزء الأول من موسوعته «دولة الإسلام فى الأندلس- من الفتح إلى بداية عهد الناصر» عن «الهيئة المصرية العامة للكتاب- القاهرة»، ويرى «عنان» أن بن نصير من أعظم الزعماء والقادة، الذين وجهتهم الخلافة إلى الغرب، أصبح أميرًا على ولاية أفريقية فى عهد الخليفة الأموى الوليد بن عبدالملك، واستطاع أن يبسط سلطان العرب على شمالى أفريقيا كله فى البر والبحر، ويذكر عنان، أنه لم يبق من ثغور شمال أفريقية بيد النصارى سوى ثغر سبتة الواقع فى نهاية البحر الأبيض المتوسط شرق طنجة، وكانت من أملاك أسبانيا، ويحكمها زعيم من الفرنج يدعى «الكونت يوليان»، ويؤكد عنان: «كان موسى يتوق إلى افتتاح هذا المعقل الحصين، على أن مشاريعه فى الفتح لم تكن تقف عند سبتة بل تجاوزها إلى ما وراء ذلك البحر الشاسع، الذى عرف عنه العرب كثيرًا عن شواطئه الشرقية والجنوبية، ولكنهم لم يعرفوا بعد شيئا أولم يعرفوا سوى القليل عن شواطئه الشمالية والغربية، كان موسى يتوق إلى افتتاح ما وراء ذلك البحر من الممالك والأمم المجهولة».
كانت شبه الجزيرة الأسبانية هى بداية موسى بن نصير لفتح «الأمم المجهولة»، التى تقع ما وراء البحار، وكانت تعيش حسب تأكيد عنان فى «حوادث وأزمات خطيرة، وكان المجتمع الأسبانى يعانى صنوف الشقاء والبؤس، ومزقته عصور طويلة من الظلم والإرهاق والإيثار، وكان الشعب فى حالة يرثى لها من الحرمان والبؤس، يعانى من ضروب الظلم والعسف والإرهاق، وتسلبه فروض العبودية والرق، وكان كتلة مهيضة من طبقة فقيرة وسطى، ومن جمهرة من الزراع شبه الأرقاء، ومع ذلك كان يقع عليه إلى جانب هذه الفروض والمعازم الفادحة عبء الحرب والدفاع عن الوطن، وكان يهود الجزيرة كتلة كبيرة عاملة، ولكنهم كانوا موضع البغض والتعصب والتحامل، يعانون أشنع ألوان الجور والاضطهاد، وكانت الكنيسة منذ اشتد ساعدها ونفوذها تحاول تنصير اليهود، وتتوسل إلى تحقيق غايتها بالعنف والمطاردة».
هكذا كان حال أسبانيا حينما فتح العرب أفريقية واقتربوا من شواطئ الأندلس، وبينما كان موسى بن نصير يراقب الوضع فيها لتحقيق الوصول إلى «الضفة الأخرى من البحر»، جاءته رسالة من حاكمها الكونت يوليان يعرض فيها تسليم معقله، ويدعوه إلى فتح أسبانيا، ويذكر عنان، أن موسى استجاب لدعوة الكونت، واهتم بمشروعه أعظم اهتمام، و«كان قد وقف على أحوال أسبانيا وخصبها وغناها، واستطاع أن يقدر أهمية مثل هذا الفتح، وجليل مغانمه ومزاياه، فلما علم من يوليان وحلفائه ما تعانيه من أسبانيا من الخلاف والشقاق، وما يسودها من الانحلال والضعف، ورأى مما يعرضه يوليان من تسليم سبتة وباقى معاقله، وتقديم سفنه لنقل المسلمين فى البحر، ومعاونته بجنده وإرشاده، أن الفوز ميسور محقق، فكتب إلى الوليد بن عبدالملك يخبره بأمر المشروع، فكتب إليه الوليد أن يختبره بالسرايا «الحملات الصغيرة» وألا يزج بالمسلمين إلى أهوال البحر».
كان هناك ما يرد على تحذير الوليد بن عبدالملك من «أهوال البحر» وهو، حسب «عنان»، خوض المسلمين المعارك الحربية فى هذه المياه حين غزو «صقلية» و«سردانية» و«الجزائر الشرقية»، وكان البحر الذى يفصل بين أفريقية والأندلس ضيقا سهل العبور. هكذا تهيأت كل الظروف لحلم «بن نصير»، فبدأ وحسب عنان فى تجهيز جيشه من العرب والبربر فى شهر أبريل عام 711، وكان قوام الجيش سبعة آلاف بقيادة طارق بن زياد، وكان وقتئذ حاكمًا لطنجة، وينقل «عنان» عن صاحب كتاب «الإمامة والسياسة» صفات لطارق: «طويل، أشقر، صاحب حول فى عينيه، وبيده شلل، وتلك الصفات ترجح انتماءه إلى الجنس البربرى، الذى يكثر بينهم الطول والشقرة»، ويضيف «عنان»: «كان جنديًا عظيمًا ظهر فى غزوات المغرب بفائق شجاعته وبراعته، وقدر موسى مواهبه ومقدرته واختاره لحكم طنجة وما يليها، وهى يومئذ أخطر بقاع المغرب الأقصى وأشدها اضطرابًا، ثم اختاره لفتح الأندلس، فعبر البحر من سبتة بجيشه تباعًا، ونزل بالبقعة الصخرية المقابلة، التى تحمل اسمه إلى اليوم «جبل طارق»، وذلك فى يوم الاثنين 27 إبريل «مثل هذا اليوم» عام 711.