ولما جاءت استغاثة طارق إلى موسى بن نصير أدرك أن مخاوفه من انطلاق طارق في فتوحه بعد معركة وادي بكة لها ما يسوغها، وأسرع موسى بإعداد جيش مكون من ثمانية عشر ألفا من خيرة جنده، وكان معظمهم من العرب والبربر الذين عرفوا بقوة الشكيمة وشدة المراس، وممن اشتهروا ببلائهم في ميدان الحروب ببلاد المغرب، وغادر موسى بلاد المغرب على عجل، وقسم موسى بن نصير جيشه بحسب القبائل ليسهل عبورها إلى الأندلس دون أن تقع فوضى في صفوف الجند، وفي رمضان عام 93ه (يونيه 712م) كان موسى ابن نصير قد غادر المغرب ووصل إلى الجزيرة الخضراء في الأندلس، وشيد بها مسجدا وانتظر هناك حتى تم عبور سائر الجند واطمأن على سلامتهم وحسن ترتيبهم، وفي تلك الأثناء أسرع يوليان إلى لقاء موسى بن نصير وعقد معه مجلسا حربيا للتشاور في هذا الموقف الخطير، وقرر هذا المجلس الحربي أن الضرورة تقضي بالسيطرة أولا على المعاقل التي تركها طارق والتي باتت خطرا يتهدد المسلمين، وبعث موسى بن نصير عقب هذا المجلس الحربي الهام رسالة إلى طارق بن زياد يأمره فيها بالانتظار في طليطلة، وألا يقوم بعمل حربي إلا بإشعار آخر.

ورددت بعض المراجع أن موسى لم يقدم على هذا العمل والعبور إلى الأندلس إلا منافسة لطارق ورغبة استبدت به لينال بدوره نصيبا كبيرا من الغنائم، وأن الحسد كان يأكل قلبه، وأنه صمم على محاسبة طارق على أعماله، وأنه رأى أن يتولى بنفسه فتوحا أخرى أعظم مما قام به هذا القائد.