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