فقيل له: ألا تدعو لأمير المؤمنين؟ فقال: هذا مقام لا ندعو فيه لغير الله ﷿، فسُقُوا حتى رَوُوا، ثم خرج موسى غازيًا (١)، وتتبع البربر، وقتل فيهم وسبى، فلما رأى البربر ما نزل بهم، استأمنوا، وبذلوا له الطاعة، فقبل منهم، وولَّى عليهم واليا، وترك عندهم من يعلمهم القرآن وشرائع الإسلام، ورجع إلى إفريقية، ولم يبق بالبلاد من ينازعه من البربر، ولا من الروم.
فلما استقرت له القواعد، كتب إلى مولاه طارق بن زياد، وكان استعمله على طنجة وأعمالها يأمره بغزو الأندلس في جيش من البربر، وليس فيه من العرب إلا قدر يسير، فامتثل طارق أمره، وركب البحر من سبتة إلى الجزيرة الخضراء من بر الأندلس، وصعد إلى جبل يعرف اليوم بجبل طارق؛ لأنه نُسب إليه لما حصل عليه، وكان صعوده إليه يوم الاثنين، لخمسٍ خلون من رجب، سنة اثنتين وتسعين للهجرة.
وذُكر عن طارق: أنه كان نائمًا في المركب وقت التعدية (٢)، وأنه رأى النبي ﷺ، والخلفاء الأربعة ﵃ يمشون على الماء حتى مروا، فبشَّره النبي ﷺ بالفتح، وأمره بالرفق بالمسلمين، والوفاء بالعهد، ولما حلَّ طارق بالجبل، كتب إلى موسى بن نُصير: إني فعلت ما أمرتني، سهَّل الله تعالى لي الدخول، فندم موسى على تأخره، وعلم أنه إن فتح، نُسب