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