Летом того года на пути из Генуи в Чивитавеккью плыли две военные галеры с ценным грузом на борту, принадлежавшие папе римскому Юлию II. Когда первая галера проходила мимо острова Эльба, ее капитан Паоло Виктор обратил внимание на небольшое судно, похожее на купеческую фелюку, которое уже долгое время шло в отдалении от его галеры параллельным курсом. Он особо не обеспокоился, видя неизвестное судно – может быть, пиратское. Ведь на военной галере имелись и орудия, и отряд солдат, так что он посчитал невозможным нападение на нее небольшого пиратского судна. Внезапно это судно резко повернуло и прижалось к борту галеры. Палуба папской галеры была буквально осыпана градом стрел. А затем с этого судна за считанные секунды на борт галеры перелезли десятки пиратов во главе с предводителем, у которого была ярко-рыжая борода. Начался жестокий абордажный бой. Экипаж галеры сумел все же прижать пиратов к борту и повязать их. Рыжебородого предводителя привязали к мачте.

Папские солдаты бросились на пиратскую фелюку в поисках добычи, оставив оружие на палубе галеры. Тут-то и произошло неожиданное. Предводитель пиратов, а это был Арудж, сумел освободиться от наспех завязанных веревок, заколол капитана галеры и освободил от веревочных пут своих соратников. Безоружные папские солдаты сдались. Мавры-гребцы на галере встретили пиратов радостными криками.

Арудж заставил обезоруженную команду галеры раздеться и запер ее в трюме, а затем приказал своим пиратам облачиться в одеяния папских солдат. Он взял на буксир пустую фелюку и стал поджидать подхода второй галеры. Ее капитан спокойно наблюдал за приближением захваченной пиратами галеры и решил, что команда первой галеры буксирует плененное пиратское судно. Приблизившись ко второй галере, пираты, облаченные в костюмы папских солдат, быстро овладели ею, повязав оторопевшую от изумления команду.

Затем Арудж высадил всех оставшихся в живых папских воинов на берег, чтобы весть о его блестящей победе быстрее разнеслась по христианским странам. С того времени за Аруджем и закрепилась кличка Барбаросса – «Красная борода». (До него так называли германского императора Фридриха I Барбароссу, одного из вождей 3-го Крестового похода, за наличие у него густой рыжей бороды.) Весь католический мир был просто потрясен этим дерзким налетом на папские галеры. Папа Юлий II обратился к королю Кастилии и Арагона Фердинанду с просьбой разорить базы пиратов-мусульман. Но сделать это оказалось совсем не просто.

В 1516 году умер король Кастилии и Арагона. В Испании началась смута междуцарствия, так что испанским дворянам стало не до Северной Африки. Именно тогда Арудж обратился к султану Туниса с предложением отбить у испанцев крепость Бужи (теперь город Беджаия). Султан охотно согласился на предложение пирата и обещал выделить им в помощь несколько кораблей и припасы. Ведь при возвращении Бужи султану Туниса под его контроль стали бы (как и ранее, до захвата города испанцами) исправно поступать налоги с многочисленных жителей города, в котором было тогда 8 тысяч домов. В случае успеха пираты надеялись, что султан разрешит им использовать гавань Бужи как базу для дальнейших нападений на испанские суда. Арудж заручился также поддержкой горских берберских племен.

Он был уверен, что жители Бужи сами откроют ворота крепости, потому что ненавидят своего правителя-бея. Всего за 10 лет до этого, когда к городу подошли испанские корабли с войсками, султан не организовал оборону города, а бежал с охраной, евнухами и гаремом в горы. Пришлось и многим жителям покинуть родные дома. Испанцы без единого выстрела заняли крепость, и город был отдан на разграбление солдатам. Бей начал переговоры с испанцами, изъявил покорность испанским владыкам, готовность платить им ежегодную дань и, главное, обязался изгнать из города пиратов. А ведь до этого жители города – состоятельные мавры и иудеи, изгнанные ранее из Испании, снаряжали пиратские корабли и получали часть добычи при захвате пиратами судов христиан и ограблении прибрежных поселений Испании и Италии. Испанский командующий граф Пьетро Наваррский разрешил бею возвратиться в разграбленный дворец. Он заставил жителей города укрепить стены касбы – крепостной цитадели, построил в ней замок и затем разместил там испанский гарнизон.

Арудж высадился с несколькими десятками пиратов на разведку и близко подошел к цитадели. Испанцы открыли артиллерийский огонь, и ядром у Аруджа оторвало левую руку. Пираты вынуждены были отступить (по другой версии его биографии, Аруджу отрубили руку ранее в абордажной схватке при захвате вместе с братом Xайр-эд-Дином испанского военного корабля). Но через полгода Арудж вновь в строю. Тунисские ремесленники изготовили ему протез из серебра. Искусственная рука могла двигаться и даже сжимать рукоять кинжала.

Неукротимый пират разграбил поселения на острове Минорка (Балеарские острова), а затем подошел к Корсике. Местные жители, наслышанные о бесчинствах пиратов, выплатили Аруджу большую сумму денег, лишь бы пираты не высаживались на берег. Затем в Тирренском море он взял на абордаж несколько торговых судов.

Но мысль о взятии Бужи не оставила Аруджа. Он вновь отправился под ее стены. Старую арабскую касбу он взял с налета. Испанцы засели в замке. Попытка штурма его привела к гибели 400 пиратов. Арудж приказал начать осаду. Испанский губернатор Орана послал на помощь осажденным эскадру. Подойдя к Бужи, испанские корабли начали бомбардировку осаждавших. Союзники (кочевники-кабилы) с началом бомбардировки оставили город и ушли в горы. Пришлось отступить и Аруджу. В начале нападения на Бужи пираты завели свои корабли в устье реки. Возвратившись к устью, Арудж увидел: вода в реке резко спала и корабли оказались на мели. Пришлось ему с пиратами двигаться по горным тропам пешком. Пройдя 80 миль, пиратский отряд подошел к городу Джиджелли, расположенному на небольшом острове у побережья.

Город, насчитывавший всего 500 домов, был окружен мощной стеной. Этим городом не раз пытались овладеть – и бей Бужи, и султан Туниса, и испанцы. Но Аруджу, который был известен как храбрый боец с неверными, жители города добровольно открыли ворота и даже согласились платить подать на содержание «борцов за веру».

После смерти короля Фердинанда в 1516 году жители Алжира восстали против испанской оккупации. Восстание возглавил араб Селим ат-Туми, который и стал алжирским эмиром. Испанский гарнизон перешел на островок у входа в гавань в форт Пеньон, где дон Мартин де Варгас с гарнизоном всего из полутысячи солдат стал ожидать помощи с моря или по суше из Орана. Муфтии посоветовали Селиму ат-Туми позвать на помощь Барбароссу.

Арудж (Хорук), Барбаросса I (слева), и Ацор-Хайр-эд-Дин, Барбаросса II

Предвидя перемены в Алжире, Арудж и Xайр-эд-Дин заблаговременно перевели пиратские корабли с Джербы у берегов Туниса на скалистый алжирский архипелаг Агелли. Поэтому получив приглашение, Арудж послал брату приказ немедленно направиться к Алжиру со всем пиратским войском. А сам с 60 бойцами пошел туда же из Джиджелли.

Прибыв в Алжир, Арудж дождался быстрого прибытия брата со всеми пиратскими кораблями, удавил Селима и провозгласил себя правителем Алжира, начав даже чеканить собственную монету со своим профилем на ней. Барбаросса обложил высокими налогами город и окрестных племенных вождей, даже более высокими, чем взимали испанцы. Против новоявленного тирана составился заговор. Но среди заговорщиков нашелся предатель, ренегат (бывший христианин). Он и выдал заговорщиков Аруджу, который в ближайшую пятницу призвал их на пятничную молитву в главную мечеть, а заодно пригласил туда и богатейших горожан. Едва приглашенные на молитву вошли в мечеть и расстелили молитвенные коврики, как приближенные Аруджа – турки – заперли все двери, бросились на молившихся и порубили их саблями. Затем по приказу Аруджа обезглавленные тела были привязаны к хвостам ишаков, их проволокли по улицам города и сбросили в яму с нечистотами.