وقد برز أمام المرابطين فجأة خطر خارجي بحري استهدف الجزر في شرق الأندلس, إذ قام أسطول لأهل بيزا وجَنَوَة بالهجوم على جزر البالئار, وقدّرت رواية ابن الكردبوس عدد قطعه بثلاثمائة,حيث دخل الأسطول جزيرة يابسة أولًا فنهبها وسبى أهلها وقام صاحب الجزر مبشر ناصر الدولة بالدفاع عن كبرى الجزر ميورقة حتى توفي، واستطاعت سفينة يقودها أبو عبد الله بن ميمون اختراق طوق الحصار والتسلل خارج مياه الجزيرة لطلب النجدة من المرابطين، لكن الجزيرة سقطت وحل بها ما حلّ بأختها قبلًا, وحينما وصل الأسطول المرابطي ذي العدد المماثل حسب الرواية ذاتها، وجد عمران الجزيرة قد دُمّر فعمل على إعمارها من جديد, وارتد إليها من سكانها من كان قد لاذ بالفرار إلى الجبال, وردّ المرابطون اِثر ذلك على العملية سنة 515هـ بإرسال حملة بحرية على قِلَّوْرِية شرقي صقلية التابعة لملك صقلية وقادها ابن ميمون الذي أصبح قائد الأسطول لدى المرابطين.

وفي خلال العقد الثاني من حكم علي بن يوسف برز الفونسو الأول ملك أراغون المقلب لدى الأسبان بالمحارب AL Fonso Barallador والذي تدعوه الروايات العربية بابن رذمير, وقد دأب على مهاجمة مملكة سرقسطة بمساعدة ابن هود (عبد الملك ابن المستعين) المخلوع عن عرش سرقسطة حتى أن العديد من أمراء سرقسطة المرابطين استشهدوا أثناء عمليات الدفاع عنها, وأخيرًا ركز الفونسو عمله الحربي على مدينة لاردَة، فتجمعت قوات مرابطيه من مناطق الأندلس تحت راية الأمير تميم حاكم بلنسية، وواجهت الملك الأرغوني فاضطرته لفك الحصار عن لارده بعدما أوقعت به خسائر جسيمة؛ تبلغ حسب رواية صاحب روض القرطاس عشرة آلاف فارس، وربما كان في ذلك شيء من مبالغة.