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