При встрече с родосскими рыцарями Арудж попал в плен. Около двух лет он находился в рабстве. Все это время Арудж был прикован к скамье гребцов и выдавал себя за немого. Имени его никто не знал, и ему дали прозвище по цвету его бороды и волос — Барбаросса, что означает Рыжая Борода.
Улучив удобный момент, Арудж сумел разорвать цепи и сбежать. Ему удалось уговорить одного купца доверить ему небольшое военное судно для крейсирования у берегов Родоса. Но в первом же походе начинающий пират потерпел поражение. Чудом Арудж спасся.
Нищета заставила его наняться носильщиком, но эта работа была Рыжей Бороде явно не по душе. Он устроился кормчим на бригантине, сооруженной двумя купцами для морских разбоев. Однако это место не соответствовало способностям, которыми был наделен Арудж.
Лидер по натуре, он сумел привлечь на свою сторону большую часть экипажа и, воспользовавшись случаем, раздробил командиру топором голову и занял его место. Оставаться рядом с Турцией было опасно, поэтому Арудж решил отправиться к берегам Африки.
По пути он заехал домой и отдал живущей в бедности матери часть добычи. Братья, увидев, что Аруджу удалось разбогатеть за короткий срок, бросили свое ремесло и присоединились к нему.
За короткий срок Аруджу удалось одержать несколько побед, и теперь в его распоряжении находилось три корабля. С богатой добычей Арудж направился в Тунис, чтобы завоевать расположение султана Мулей-Ахмеда. Султан был польщен богатыми подарками, приказал выдать пиратам по красному плащу и по 200 червонцев.
Около двух месяцев Арудж провел в Тунисе в пирах, а потом вновь вышел в море. Султан отдал пиратам в пользование свои лучшие корабли. Однако союз с Мулей-Ахмедом продлился недолго. Султан хотел иметь большую часть добычи, что пиратам было не по душе.
На острове Желве Рыжая Борода заключил союз с независимыми корсарами. Удача сопутствовала пиратам, и вскоре об их подвигах стали ходить легенды. Корабли Аруджа смело курсировали даже у берегов Италии.
Однажды на пиратов напали две хорошо вооруженные испанские галеры. Почти половина морских разбойников была убита. Сам Арудж попал в плен. Но он не унывал. Большая часть испанцев перешла для грабежа на бригантину. Улучив момент, Арудж сумел достать кинжал и вонзить его в горло капитану неприятеля. Рыжая Борода освободился сам и освободил своих товарищей. Пираты схватили оружие, оставленное испанцами. Вновь вспыхивает сражение, победу в котором одерживают пираты.
Арудж приказал пиратам переодеться в одежду испанцев и идти ко второй галере. Испанцы сочли дело сделанным и потому спокойно подпустили к себе галеру неприятеля, тащившую на буксире пиратскую бригантину. Опомнились испанцы только тогда, когда сопротивляться было бессмысленно.
В сражении Арудж потерял много людей, и теперь ему требовалось подкрепление. Это заставило его помириться с турецким султаном. Арудж пообещал Мулей-Ахмеду завоевать для него Буджию. Такое предложение показалось султану заманчивым, он охотно согласился и в начале 1514 года выделил в распоряжение Аруджа два корабля и конвой со съестными припасами.
Однако при первой же попытке приблизиться к Буджии Арудж был ранен, ядро раздробило ему руку. От намерения взять город пришлось на время отказаться. Ампутация прошла неудачно, и Арудж оказался на грани жизни и смерти. Но силы воли ему было не занимать. Он сумел выкарабкаться, а искусные хирурги сделали ему серебряную руку, которая могла двигаться на пружинках.
В 1515 году Арудж совершенно излечился и был готов к новым подвигам. Он вновь осадил Буджию. Но напрасно пиратские корабли обстреливали город — крепостные стены выдержали шквал снарядов. В одной из атак пушечное ядро разорвало брата Аруджа Исхака. Арудж отступил, с остатками армии он нашел приют у своего союзника в Джиджели.
23 января 1516 года скончался испанский король Фердинанд Католик. Смерть его явилась для арабов сигналом к действию. Они решили, что негоже платить дань Испании и нужно бороться за свободу. Алжирцы избрали своим шейхом Селима, но у нового правителя не хватало смелости самому вступить в сражение с испанцами. Он послал гонцов к Аруджу. Селим прислал знаменитому пирату подарки и предложение стать губернатором Алжира. Арудж, надеясь в будущем стать правителем арабского мира, согласился.
С немногочисленным отрядом он прибыл в Алжир. Горожане встречали его с ликованием. Вскоре к Аруджу присоединились 300 турецких солдат из Туниса. Вместе с братом Хайраддином он готовил заговор против шейха Селима, хотя на людях всячески его поддерживал. Когда прибыли последние подкрепления, Арудж принялся обстреливать испанский гарнизон в Пеньоне. Под одобрительные крики алжирцев он сорвал флаги Испании. Штурмовать Пеньон он не стал — испанцы заперлись в неприступной крепости, и он не хотел терять своих людей. Постепенно горожане стали привыкать к мысли, что всем в Алжире заправляет Арудж. Убедившись, что народ его поддерживает, Арудж напал на дворец шейха, перебил охрану, а самого Селима задушил.
Эйтеми, сын Селима, бежал в Испанию, где нашел приют у старика Хименеса. Алжирцы, недовольные убийством Селима, составили заговор против Аруджа, но на них донес христианский невольник. Предводитель пиратов приготовил для своих противников жестокую казнь. Он пригласил знатных алжирцев в мечеть на праздник. Как только вельможи вошли в здание, на них накинулись турецкие янычары. Они отрубили головы двадцати двум алжирцам, привязали их обезглавленные тела к лошадям и проволокли по улицам города. Это был хороший урок для всех недовольных правлением шейха-пирата.
Хименес отправил для усмирения Аруджа эскадру кораблей под командованием Диего де Веры. Арудж пошел на хитрость. Городские ворота были отперты, а солдаты убраны со стен. Испанцы ворвались в город, не встречая сопротивления, но попали в ловушки, расставленные Аруджом. Хитроумный пират приказал вырыть на улицах Алжира глубокие ямы, в дно которых забили заостренные колья. Ямы замаскировали землей. Множество испанцев погибло, провалившись в ловушки. Диего де Вера с трудом избежал плена, а по возвращении в Испанию его ждала немилость и опала.
Арудж стал хозяином алжирского побережья. Ему помогала даже природа — невиданной силы буря разметала и потопила множество испанских кораблей. Алжир стал столицей пиратского государства.
Арудж оказался на гребне славы, но конец его завоеваниям был близок. В 1517 году он захватил Тенес. Вскоре после этого к нему прибыла делегация из Тлемсена, посланцы города просили Аруджа навести порядок в Тлемсене. Мулей-бу-Хамуд, поддерживаемый испанцами, захватил власть и обложил местное население данью.
Арудж с войсками поспешил к городу. Брат Хайрадцин прислал в помощь ему два галиона с запасом пороха и ядер. Навстречу ему выступила армия Мулейбу-Хамуда. Но что могли противопоставить арабы, вооруженные лишь луками и копьями, хорошо обученным турецким наемникам Аруджа с их ружьями и пушками! Арабы бросились врассыпную после первого же залпа пушек Аруджа.
Жители города открыли ворота перед освободителем, но взяли с Аруджа обещание, что он восстановит на престоле Мулейбу-Заина, брата тирана. Арудж давал клятвы с той же легкостью, с какой впоследствии их нарушал. Ровно через четыре часа султан и его приближенные были повешены во внутренних покоях дворца. Еще несколько десятков человек Арудж утопил собственноручно.
Девять месяцев он правил Тлемсеном, а перед своим отъездом в Алжир умертвил 70 богатых горожан. Это стало последней каплей, переполнившей чашу терпения людей, они подняли восстание. К Тлемсену приближалась испанская армия, вызванная Мулейбу-Хамудом.
Арудж вместе с сотней преданных воинов, захватил сокровища Тлемсена, бежал из города. На дороге, ведущей в Алжир, его встретила испанская конница. Арудж бросил сокровища, но испанцы не прельстились богатством и кинулись в погоню за пиратом. Окруженный ими, он яростно отбивался, пока один из испанцев не пригвоздил его копьем к земле. Отрубленную голову Аруджа насадили на древко знамени и отправили в Испанию. Там страшный трофей перевозили из города в город, наводя ужас на простых испанцев.
Аруджу Барбароссе было тридцать шесть лет, из которых он успел поцарствовать двадцать месяцев. Правители христианской Испании могли вздохнуть свободно — они устранили опаснейшего противника из мусульманского мира. Но у Барбароссы остался брат — Хайраддин, который решил продолжить дело, начатое Аруджем.
Хайраддин правил в Алжире, когда узнал, что Арудж убит. Он сразу понял, что испанцы захотят развить свой успех и нападут на Алжир. В спешном порядке он усиливает гарнизон города, возводит новые укрепления.
Вице-король Сицилии Хуго де Монкада, собрав многочисленную армию, явился 17 августа 1518 года к стенам Алжира. Он послал к Хайраддину парламентера с требованием немедленной сдачи. В противном случае испанский военачальник обещал предать его лютой смерти, как его брата Аруджа.
Хайраддина не испугало это заявление. Он передал де Монкаде свой ответ: «Дети пророка не страшатся смерти... Знайте, что пока в Алжире останется в живых хоть один турок, вы не проникнете в него. Меч решит, кто из нас более заслуживает владычествовать над морем. Господь сам сделается нашим судьей!»
Ответ алжирского султана привел испанцев в ярость. Де Монкада хотел немедленно идти на штурм, но его отговорил командующий артиллерией, который ждал прибытия арабов, посланных султаном Тлемсена.
Ожидание испанцев затянулось на шесть дней. А после этого налетел северный ветер, принесший с собой свирепую бурю. Якоря не могли удержать корабли, стоявшие на рейде. Шторм переворачивал их и разбивал о прибрежные скалы. 26 кораблей уничтожила буря, около 4 тысяч испанских солдат погибло. Хайраддин, возблагодарив Аллаха за помощь, лично возглавил армию и вышел из города. Он напал на лагерь испанцев, которые, прижатые к морю, отчаянно защищались.