Летом 1570 года султан призвал Улуджа-Али в Константинополь для участия в совместной экспедиции против испанцев. Выполняя волю повелителя, алжирский бейлербей собрал свою эскадру и направился в столицу. По пути, возле мыса Пассаро, он встретил четыре мальтийских галеры под командованием Франциско де Сент-Климента, капитан-генерала Мальтийского ордена Они перевозили большую денежную казну и стали настоящим подарком для пиратов.
Силы двух сторон были неравны, и три галеры стали добычей Улуджа. Шестьдесят рыцарей попали в плен, что стало настоящей катастрофой для сил Ордена Сам Сент-Климент избежал плена и на оставшейся галере благополучно вернулся на Мальту. Слухи о поражении вызвали гаев толпы, и Сент-Клименту с трудом удалось спастись от линчевания. Однако магистр был вынужден передать его суду. За малодушие и предательство он был приговорён к смертной казни. Его тайно задушили в камере, тело зашили в кожаный мешок и бросили в море.
Между тем победа у мыса Пассаро заставила Улуджа-Али изменить свои планы. Он взял обратный курс на Алжир, чтобы с размахом отпраздновать свою победу.
Впрочем, далеко не всем нравилось правление нового бейлербея. Задержки с денежными выплатами заставили янычар из алжирского гарнизона поднять мятеж. Улудж-Али не стал наказывать янычар, на ятаганах которых держалась его власть, а поступил в свойственной для него манере. Он передал янычарам свои галеры и позволил им грабить всех, кого они встретят на своём пути, в качестве платы за службу.
Подавив сопротивление в своих владениях, он был вынужден подчиниться приказу султана и отправился к берегам Морей для объединения сил с флотом Али-паши, который готовился сокрушить последние очаги сопротивления в Греции. Объединённый флот направился к самой крупной из колоний Венеции — Кипру. Султан давно хотел завоевать этот остров и вскоре нашёл повод для объявления войны. Улудж-Али участвовал в переправке турецкой армии. 3 июля 1571 года турки высадились на Кипре и вскоре осадили Никосию — главный административный центр острова.
Ещё до захвата Кипра папа римский Пий V обратился к европейским монархам с просьбой о помощи. На призыв откликнулся испанский король Филипп II. Он снарядил большой флот под командованием Джованни Дориа. Свой контингент предоставили и некоторые итальянские государства во главе с неаполитанским Великим констеблем Марко Антонио Колонной. К испанскому флоту присоединился венецианский, во главе с Джовани Зане. В общей сложности объединенная армада насчитывала 206 кораблей, из которых 12 были галеасами, а все остальные боевыми галерами. Они должны были перевезти 48 тысяч солдат для оказания помощи венецианцам, сражавшимся на Кипре. Если бы среди руководителей этой экспедиции было хоть какое-то единство, они могли бы сокрушить турок, но единства не было. Пока союзники пререкались, турки получили подкрепления, и 9 сентября Никосия пала. Однако сопротивление продолжала Фамагуста, где укрепился шеститысячный венецианский гарнизон под командованием Марко Антонио Брагадино. Турецкая стотысячная армия начала бесконечные штурмы этой крепости. Видя бесперспективность сопротивления, 31 июля Брагадино согласился на капитуляцию.
