٢١٢ هـ، بدأت الأساطيل البيزنطية تهاجم القوات الإسلامية فيها، ففي عام ٢١٤ هـ وجه الأمير عبد الرحمن الأوسط (٢٠٦ - ٢٣٨ هـ)، حملة بحرية خرجت من ميناء طرطوشة إلى صقلية لتعزيز الحامية الإسلامية فيها (٢٨٢).
وفي عام ٢٢١ هـ خرج أسطول أندلسي من ثغر طركونة والجزائر الشرقية، وهاجم مرسيلية وما حولها وأثخن فيها، فكانت هذه الحملة مقدمة لحملات أخرى متعاقبة أفلحت في إقامة مراكز عربية في جنوب فرنسا وشمالي إيطاليا (٢٨٣). ويبدو لنا أن الجزائر الشرقية (البليار) عقدت عهداً مع حكومة الإمارة، على الأقل فيما يتعلق بشؤون البحر، ودليلنا على ذلك أن الأمير عبد الرحمن الأوسط سير أسطولاً من ثلثمائة مركب عام ٢٣٤ هـ إلى أهل الجزائر الشرقية لنقضهم العهد، وإضرارهم بمن يمر بهم من مراكب المسلمين (٢٨٤). ويبدو أنها كانت حملة تأديبية وليست فتحاً منظماً بدليل قدوم رسالة من أهل الجزائر إلى الأمير في عام ٢٣٥ هـ يستعطفون فيها الأمير ويطلبون السماح، فاستجاب لهم (٢٨٥).
مع كل هذا، فإن البحرية الأندلسية كانت لا تزال محدودة في إمكانياتها ووسائلها، فلم تكن لديها القواعد والمحارس والسفن الكافية لحماية جميع سواحلها ولا سيما الغربية منها، ولهذا عجزت عن حمايتها عندما هاجمتها أساطيل النورمان عام ٢٢٩ هـ وعاثت فساداً في السواحل الغربية، وفي مدينة إشبيلية (٢٨٦). ولما كان الأسطول الأندلسي مرابطاً على الساحل الشرقي، فقد اعتمدت حكومة الإمارة في صد خطر النورمان على جيوشها البرية، واستعانت بقوات من الثغر الأعلى المدربة على حرب العصابات (٢٨٧).
وكان لهذا الهجوم النورماني أثر كبير على الأندلس، حيث أدى إلى الاهتمام بالسواحل الغربية للأندلس وبناء التحصينات فيها، حيث بني سور إشبيلية (٢٨٨)، كما