Флот Аруджа пополнялся с неслыханной быстротой: слухи об его фантастической удачливости уже успели облететь все Средиземноморье. Его потайные стоянки и убежища были далеко от берегов Африки, и Арудж выжимал из них все преимущества, какие они могли дать. Одна из таких стоянок находилась, например, в Корсиканском проливе у самых берегов Италии. И выходя из нее на охоту, пираты считали ниже своего достоинства сменить, скажем, флаг с полумесяцем на флаг с крестом или поменять тюрбан на шапку. Они не скрывались, их набеги были молниеносны. Под свист плети рабы проворно орудовали тяжеленными веслами, а те, кто не выдерживал, находил вечный покой в морских глубинах. Ночью пиратские корабли были бесшумными призраками, днем - колесницами морского дьявола, несущими смерть. На борт они принимали только крупный товар: для дублонов, дукатов, пиастров или цехинов у них существовал особый «кошелек» - полые мачты, и раззявы-купцы сами заботились о том, чтобы он всегда был набит «под завязку».
Весной 1504 года Арудж совершил одну из самых блестящих и остроумных операций на море, какие знает история. Тот день, по свидетельствам очевидцев, был ясным и безоблачным, а море - каким его изображают нынче на рекламных проспектах Лазурного Берега. Из Генуи в Чивитавеккью не спеша продвигались две военные галеры с ключами святого Петра на флагах. Никакой войны папа Юлий II не вел, и, значит, на галерах мог оказаться какой-нибудь ценный груз. Арудж моментально оценил обстановку и принял решение. Было около полудня, солнце припекало вовсю. Погода не располагала папских моряков к излишней бдительности, да и берега Италии проплывали совсем рядом. Первая галера вырвалась далеко вперед, вторая замешкалась где-то за горизонтом.
И вот, когда первая галера миновала остров Эльба, ее матросы заметили, что их догоняет быстроходный корабль, распустивший все свой крылья. Палуба его была безлюдна, но у рулевого и у капитана, маячивших на корме, по мере приближения все явственнее можно было различить на головах цветастые чалмы. Корабль Аруджа шутя догнал неповоротливое судно, на его палубу обрушился ливень стрел. Пока беспечный экипаж искал оружие, галера была взята на абордаж, и все было кончено в считанные минуты. Пираты раздели тех, кто остался в живых, заперли их в трюмах, затем взяли на буксир собственное судно и, замедлив ход, преспокойно стали поджидать вторую галеру. Ее капитан сам подошел к ним бортом к борту, чтобы выразить восхищение победой над пиратами...
В другой раз Арудж вместе с Хайр-эд-Дином захватили военный корабль его католического величества, перевозивший под охраной нескольких сотен солдат губернатора и горсточку знатных пассажиров. Трюмы корабля ломились от набитых в них сокровищ. Сокровища достались маврам. Этот бой, правда, стоил Аруджу руки, отрубленной в абордажной схватке, после чего его счеты к испанцам заметно возросли.
В 1509-1510 годах почти весь Алжир был захвачен войсками Фердинанда V Католика - так теперь именовали Фердинанда II Арагонского, «завоевателя Гранады» и «открывателя Америки». Испанская речь зазвучала в портовых городах Ал-Джесаир (Алжир), Бужи (Беджаия), Оран и других. На островке Пеньон (Марин), запиравшем выход из Алжирской бухты, испанцы выстроили ряд укреплений: это был их плацдарм, направленный против мавров.
Алжирский эмир заключил с Испанией мир после того, как лишился главных своих портов, но мир этот тяготил обе стороны. После смерти Фердинанда в 1516 году Алжир восстал, восстание возглавил араб Селим ат-Туми, горожанин из Блида. Он сделал то, на что не решились испанцы: заручился поддержкой пиратов. Арудж и Хайр-эд-Дин, предвидя этот шаг, заранее перебазировались с холмистой тунисской Джербы на скалистый алжирский архипелаг Агелли, и подмога не заставила себя ждать. Алжир был взят пиратами с моря и с суши, сопротивление продолжал только скалистый остров Пеньон, где дон Мартин де Варгас с гарнизоном всего из полутысячи солдат сумел организовать превосходную оборону.
Алжирским эмиром стал теперь Селим ат-Туми, и пиратам, несомненно, улыбалась привольная жизнь. Однако их вождь рассудил иначе, не в его обычае было таскать для кого бы то ни было каштаны из огня. Он предпочитал есть их сам. Арудж испросил аудиенции у новоиспеченного монарха и направился в эмирский дворец Дженину. Селим в это время плескался в дворцовом бассейне, и освежающая прохлада настроила его на безмятежный лад. Он принял пирата прямо в купальне и отослал по его просьбе слуг: дело, по словам Аруджа, было спешным, важным и конфиденциальным. Так оно и оказалось. Поразмыслив, Арудж, видимо, решил, что, поскольку в Турции уже правил в это время Селим I, то двух Селимов на одно Средиземное море, пожалуй, многовато: как бы не произошла путаница. Дело было улажено за несколько минут: Арудж извлек эмира из бассейна за волосы, словно котенка, и профессионально задушил его.