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