Воодушевленные союзом с османами, берберийские пираты распространили свои вылазки далеко за пределы прибрежных вод Северной Африки. Хайр ад-Дин Барбаросса и его люди стали нападать на итальянские и испанские города и на Эгейские острова. В 1520-х годах Барбаросса захватывал перевозившие зерно европейские корабли и, словно Робин Гуд, раздавал добычу жителям алжирского побережья, пострадавшего от засухи. На своих судах он спасал бегущих из Испании морисков и перевозил их в безопасные места, где они присоединялись к борьбе против испанцев.
Но наибольшую славу Хайр ад-Дину принесли дерзкие нападения на испанский флот. Он топил галеры, освобождал мусульманских рабов и захватывал десятки вражеских кораблей. Имя Барбароссы вызывало страх по всему испанскому и итальянскому побережью. Количество плененных им христиан исчислялось тысячами. За дворян он требовал огромный выкуп, а простолюдинов продавал в неволю. Мусульманские корсары видели в этом высшую справедливость: в прошлом многие из них были взяты в плен испанцами и отправлены на галеры.
Испанцам срочно требовался адмирал, способный совладать с Хайр ад-Дином Барбароссой. И в 1528 году король Карл V нашел такого человека – прославленного флотоводца, генуэзца Андреа Дориа (1466–1560). Тот имел собственный флот из боевых галер и нанимался на службу к европейским монархам. По сути, он был таким же корсаром, как Барбаросса.
Дориа был выдающимся адмиралом, но Хайр ад-Дин Барбаросса оказался адмиралом от бога. За 18 лет их противостояния Дориа редко удавалось взять верх над своим рыжебородым противником. Их первое столкновение в 1530 году было весьма показательным. После короткой осады в 1529 году Хайр ад-Дин захватил испанскую крепость в Алжирском заливе. Он заставил обращенных в рабство испанцев разобрать форт и соорудить из камней мол для защиты гавани. Карл V пришел в ярость от потери стратегически важной крепости и созвал государственный совет. Андреа Дориа предложил атаковать порт Шершель к западу от Алжира. В 1530 году Дориа с отрядом испанцев высадился под Шершелем. Они освободили несколько сотен христианских рабов, однако столкнулись с ожесточенным сопротивлением со стороны населявших город морисков, которые ненавидели испанцев. Хайр ад-Дин отправил в Шершель помощь, и Дориа, побоявшись вступать в сражение с крупным османским флотом, увел свои корабли, бросив испанских солдат на берегу. Многие из них погибли, остальных взяли в плен и продали в рабство. Так Хайр ад-Дин Барбаросса нанес испанской короне два поражения и укрепил свои позиции в Алжире.
Этой победой он также поднял себя в глазах османского султана Сулеймана Великолепного, который в 1532 году пригласил его в Стамбул. Собрав флотилию из 44 кораблей, Барбаросса направился в имперскую столицу, по пути разорив побережье Генуи и Сицилии и захватив 18 христианских кораблей, которые он также разграбил и сжег. Прибыв во дворец, Барбаросса был препровожден к султану, распростерся перед ним ниц и поцеловал землю. Сулейман попросил пирата подняться и объявил, что назначает его главнокомандующим Османским флотом, т. е. капуданом-пашой, и эмиром морских провинций. На протяжении всего визита в Стамбул Хайр ад-Дин жил в султанском дворце и регулярно встречался с Сулейманом для обсуждения военно-морской стратегии. Во время прощальной дворцовой церемонии султан прикрепил к тюрбану Барбароссы золотую медаль в знак своей благодарности капудану-паше за его заслуги в расширении территории Османской империи в Северной Африке и в борьбе против испанской короны
