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