В 1504 году арабским пиратам удалось захватить две большие военные галеры папы Юлия II, которые шли из Генуи в Чивитавеккью с ценным грузом на борту. Галеры находились друг от друга вне пределов видимости, и на них не было принято никаких мер предосторожности. И вот на широте острова Эльба появился быстроходный парусник, который направился прямо к папской галере, шедшей впереди. Парусник почти поравнялся с галерой, и прятавшиеся до этого под палубой арабы приготовились к абордажу. Только теперь на папском судне заметили опасность. Но было уже поздно. После короткой схватки галера оказалась в руках пиратов. Оставшимся в живых членам команды было приказано снять одежду, в которую тут уже облачились пираты. Они замедлили ход галеры, взяли собственный корабль на буксир, как трофей, и стали ждать вторую галеру. Хитрость полностью удалась. Когда вторая галера приблизилась на достаточное расстояние, она была также захвачена. У папы стало на два военных корабля меньше.
Предводителя мавританских пиратов, который провел эту дерзкую операцию, звали Хорук (Арудж). За его рыжую бороду его прозвали Барбароссой (Рыжебородым). Он был сыном гончара Якоба Рейса, христианина, который переселился с Балкан на остров Лесбос (Митилена). После захвата острова турками он и его семья приняли ислам. Гончар имел мореходное судно, на котором доставлял на рынки свои изделия. Согласно легенде, когда подросли его сыновья, отец стал вместе с ними иногда пробавляться морским разбоем.
После смерти отца его сыновья — Хорук, Элиас, Исхак и Ацор — продолжили это занятие.
Во время одного из пиратских плаваний Арудж был захвачен в плен галерой ордена иоаннитов, а Элиас убит. Очевидно, Исхак продолжал дело отца-гончара в одиночку, так как Ацор с этого момента начинает успешную деятельность на поприще морского разбоя, принесшую ему славу самого знаменитого пирата своего времени. Он получил от турецкого султана почетное имя Хайраддина, хранителя верующих. Как и брата его Аруджа, из-за рыжей бороды его тоже называли Барбароссой. Вначале Ацор действовал в одиночку, захватывая христианские суда, чтобы собрать большую сумму для выкупа из плена своего брата Хорука (Аруджа). Однако скоро вокруг молодого и чрезвычайно удачливого пирата стало собираться все больше и больше сторонников. И несмотря на это, прошли годы, прежде чем Ацору удалось выкупить своего брата, плававшего гребцом на галере иоаннитов.
После возвращения Арудж стал во главе крупной пиратской организации, которая за большое вознаграждение оказывала услуги различным хозяевам. Своего первого крупного успеха братья добились, когда им удалось захватить хорошо вооруженную испанскую галеру, державшую курс на североафриканское побережье. Это был правительственный корабль, на борту которого находились губернатор и несколько сот солдат. Помимо золота и драгоценностей, на корабле было много пассажиров из богатых семей, за которых можно было ожидать значительного выкупа. Так как во время абордажного боя Арудж потерял руку, то честь триумфального шествия через Тунис с пленными и захваченной добычей выпала Ацору.
Наряду с пиратским товариществом Аруджа и Хайраддина на североафриканском побережье возникли многочисленные другие пиратские группы, которые имели весьма неплохой доход, нападая на торговые корабли христиан, в особенности на суда, шедшие под испанским флагом. Но Испания не оставалась бездеятельной. В течение двух лет (1509 и 1510 гг.) сильный испанский флот блокировал порты Оран, Бужи и Алжир. После этого Алжир заключил с Испанией мир, и пиратство на несколько лет затихло. Но уже в 1516 году алжирцы вновь стали призывать к борьбе против Испании. Они обратились к эмиру Селиму с просьбой стать их властелином. Селим в свою очередь попросил помощи у Аруджа. Хайраддин со своим флотом блокировал Алжир с моря, Арудж во главе пятитысячного войска вошел в город. Задушив Селима в бассейне, где тот купался, Арудж стал властелином Алжира. Он попытался распространить свое владычество на Тунис. Однако алжирцы быстро устали от его правления и начали плести сеть интриг с испанцами, чтобы избавиться от надоевшего пирата. Карл V направил испанскому наместнику в Оран 10 тыс. солдат, с помощью которых удалось окружить Аруджа и его войска возле Тлемсена. Когда Арудж попытался прорвать кольцо, он был убит в бою. Вместе с ним пали 150 пиратов. Как утверждает легенда, чтобы отвлечь преследователей, Арудж разбрасывал за собой золото и серебро. Но, по свидетельству истории, напрасно.
Испанцы раньше времени стали торжествовать по поводу смерти старшего Барбароссы. В лице его брата Хайраддина перед ними вырос новый, еще более опасный враг.
Король хотел закрепить победу и направил против Алжира флот. Это была первая из пятнадцати следовавших одна за другой попыток захватить город. Хайраддин уничтожил этот флот. Испанцы потеряли при этом более 20 кораблей и 4 тыс. человек. Войдя в Алжир, Хайраддин объявил город собственностью Османской империи и присягнул на верность турецкому султану. Султан утвердил его наместником Алжира, возвел в титул бейлербея (бей над всеми беями) и предоставил ему для борьбы против Испании 2 тыс. канониров и 4 тыс. янычар. Получив такую большую силу, Хайраддин захватил алжирские порты Бон, Колло и Шершел. Его отряды проникли даже в глубь страны. Они захватили город Константину, а также обширные области, которые были обложены данью. Хайраддин никогда не забывал обеспечивать себе милость султана с помощью богатых подарков. Но в личной жизни он оставался простым и скромным. В истории французского флота, вышедшей в 1841 году, о Хайраддине говорится следующее: "...У него были лохматые брови, густая борода и толстый нос. Его толстая нижняя губа пренебрежительно выступала вперед. Он был среднего роста, однако обладал богатырской силой. На вытянутой руке он мог держать двухгодовалую овцу до тех пор, пока та не погибала... Поистине необычайное влияние, оказываемое им на своих командиров и простых пиратов, поклонники его объясняют огромной храбростью и ловкостью этого человека, а также тем, что даже самые отчаянные его предприятия всегда оканчивались успехом.
Ум и храбрость в нападении, прозорливость и отвага в обороне, огромная работоспособность, непобедимость — все эти похвальные качества заслонялись приливами неумолимой и холодной жестокости..."
Когда в 1526 году испанцы вновь предприняли попытку возвратить Алжир, они почувствовали возросшую силу Рыжебородого. Несмотря на сильный огонь испанкой крепости Пенон, расположенной на острове неподалеку от Алжира, Хайраддин на своих маневренных судах сумел захватить испанские корабли на трудном в навигационном отношении рейде с многочисленными песчаными отмелями. Исход битвы был решен захватом испанского флагманского корабля и пленением командующего флотом. Однако после победы Хайраддин направился не в Алжир, а в Тунис, так как алжирский бей был в сговоре с испанцами. В течение приблизительно трех лет Барбаросса совершал свои пиратские операции, действуя из Туниса. Затем в 1529 году он с сильным войском появился у Алжира и наконец смог закрепиться в городе. Так как Хайраддин на собственном опыте познал значение крепости Пенон, он спустя короткое время атаковал крепость и вынудил к капитуляции ее гарнизон в составе 500 человек. Он приказал разобрать укрепления и силами рабов-христиан соорудить из камней мол, который соединил остров с материком.
Теперь Хайраддин находился на вершине власти. Его слава была так велика, что каждый рейс (капитан) североафриканского побережья считал своим долгом присоединиться к победоносному пиратскому адмиралу. Эти рейсы образовали особую компанию, которая обладала огромными средствами и большим влиянием. Команды их кораблей большей частью состояли из европейских моряков, которые попали в плен или покинули родину и приняли ислам.
В течение семнадцати лет Хайраддин Барбаросса утверждал организованное в государственном масштабе пиратское господство в западной части Средиземного Моря, не встречая при этом серьезного сопротивления. Когда турки начали поход на Вену, император Карл V назначил генуэзца Андреа Дориа адмиралом императорского флота в Средиземном море. Султан вызвал Хайраддина в Константинополь и назначил адмиралом османского флота, заявив при этом: "Отдаю под твое командование все свои корабли и доверяю тебе берега своей империи". Хотя турецкий султан, бывший в то время самым могущественным правителем на земле, официально назначил Хайраддина адмиралом османского флота, традиционная историография характеризует его и в дальнейшем как "авантюриста и предводителя пиратских банд". Противника его, Андреа Дориа, историки представляют как одного из самых крупных государственных деятелей и героев века. Насколько правдива такая характеристика, явствует хотя бы из следующего. Хайраддин сохранял верность своему султану в течение шестидесяти лет, а Дориа служил тому, кто мог больше ему заплатить: служил не только императору, но и папе против императора, Генуе против Франции и Франции против своего родного города Генуи, Франции против Испании, а также императору против короля Франции Франциска I...
