В следующем, 1536 году началась новая война между Франциском I и Карлом V. В целом она развивалась в пользу Франциска I и завершилась перемирием в 1538 году. Тем временем Турция и Венеция снова вступили в схватку. В 1536 году турки напали на южное побережье Италии и повторили атаку в 1537 году, но вскоре отозвали свои войска, чтобы объединить силы для нападения на венецианский остров Корфу. Оно не удалось, и турки вернулись в Константинополь, а Хайреддин стал совершать набеги на острова Эгейского моря. Венеция и Испания, естественно, вступили в союз против общего врага, и с помощью папы в 1538 году был собран большой христианский флот под командованием Дориа. Хайреддин был уверен в своем превосходстве и в сентябре, имея преимущество примерно три к двум, вступил в бой в районе Превезы. Сражение не было решающим, но все же дало ему семь трофеев и продемонстрировало непобедимость турецкого флота. Дориа сумел взять крепость Кастельнуово, что в устье залива Каттаро, но в 1539 году Хайреддин вернулся во главе флота из 150 парусников и снова захватил ее, а Дориа, флот которого был в три раза меньше, бессильно выжидал в районе Отранто. Это была последняя военная операция, и в 1540 году был заключен мир, невыгодный для Венеции.
Даже без Хайреддина алжирские корсары не утратили активности. Особенно один из них – Тургут, он же Драгут, наносил большой ущерб христианским берегам Средиземноморья до тех пор, пока в 1540 году не был побежден и взят в плен Джанеттино Дориа, племянником главнокомандующего. Этот успех побудил Карла V в следующем году напасть на Алжир, имея в своем распоряжении 65 галер и не менее 450 других кораблей. Плохое командование вкупе с упорным сопротивлением врага и необычайно суровой погодой разрушили его планы. Вместо вполне ожидаемого успеха экспедиция завершилась катастрофой и потерей почти третьей части флота.
В 1542 году в Италии снова началось противостояние между французами и испанцами, однако теперь участники получили возможность наблюдать потрясающее зрелище – турецкий флот под командованием Хайреддина объединился с французским флотом при осаде Ниццы. Он провел зиму 1543/44 года в Тулоне и, используя в качестве базы христианскую гавань, выполнял набеги в поисках добычи и христианских рабов. Союз был назван «нечестивым».