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