Une croisade contre les Barbaresques, ardemment prêchée depuis deux ans par le pape Pie IV, se préparait dans tous les ports d'Espagne, d'Italie et de Sicile. Mais l'armada du duc de Medina Coeli, dirigée contre Hassan, fut anéantie près de Djerba par Dragut (1560). Le beylierbey se tourna alors de nouveau contre Oran avec ses Turcs et ses régiments de Kabyles, Zouaoua et Beni-Abbès ; mais il ne réussit pas à s'emparer de la ville, non plus que de Mers-el-Kébir.

Il participa au siège de Malte où périt Dragut (1565) et fut nommé capitan-pacha en 1567. Euldj-Ali, le dernier des beylierbeys d'Afrique, fut le plus remarquable de tous. Pris dès son enfance sur les côtes de la Calabre, il avait longtemps ramé comme esclave sur les galères du sultan. Frappé au visage par un Turc, il prit le turban pour acquérir le droit de se venger. Ce renégat devint bientôt le corsaire le plus redouté de la Méditerranée, se distingua au siège de Malte et succéda à Dragut dans ses principales dignités. Appelé au gouvernement de l'Afrique en 1568, il projeta un débarquement en Espagne avec les Morisques persécutés. Profitant de l'anarchie qui régnait à Tunis, dont les habitants appelaient les Turcs comme des libérateurs, il s'en empara sans difficulté (1569), y installa une garnison de 3 000 Turcs et y fit régner l'ordre, mais il ne put prendre la Goulette, où se maintinrent les Espagnols.   Euldj-Ali augmenta et améliora la marine algérienne et c'est sous son commandement que se formèrent les hardis corsaires qui, pendant un demi-siècle, ravagèrent la chrétienté. Il commanda l'aile gauche de la flotte turque à la bataille de Lépante (1571), s'y couvrit de gloire et prit la galère-capitane de Malte avec l'étendard de la Religion. A son arrivée à Constantinople, le sultan le nomma capitan-pacha, tout en lui conservant le titre de beylierbey d'Afrique. Ainsi, dit Haedo, cet homme, sur lequel le destin sembla prendre plaisir à montrer la puissance de ses caprices, passa en quelques années des bancs de la chiourme à la dignité la plus élevée qu'un sujet ottoman pût rêver.   En son absence, Euldj-Ali fit gouverner l'Algérie par ses lieutenants Arab­Ahmed, Ramdan-Djafer, Hassan-Veneziano, qui fut le maître de Cervantès.