Арудж стойко выдерживал каторжный труд галерного раба, а тем временем его брат Ацор, будущий Хайраддин, в одиночку грабил христианские суда и собирал деньги, необходимые для выкупа Аруджа. Денег требовалось не мало, и прошло несколько лет, прежде чем Арудж вновь оказался на свободе.
Он снова стал пиратом. Но, не удовлетворившись ролью рядового пирата, Арудж взбунтовал команду и захватил корабль, стал предводителем. Он сплотил вокруг себя мелкие пиратские флотилии и вскоре стал серьезно угрожать судам христианских государств. Дело дошло до того, что в 1504 году Арудж не побоялся захватить две галеры самого папы римского. Об этой операции следует рассказать подробно.
Весной 1504 года две галеры папы Юлия II, выйдя из Генуи, следовали курсом на город Чивитавеккья. В трюмах галер находился ценный груз, а потому на палубах обоих судов располагалась многочисленная военная стража. Под этой охраной экипажи галер чувствовали себя в полной безопасности, хотя уже на траверзе острова Эльба в море было замечено какое-то неизвестное судно, идущее параллельным курсом.
По неизвестным причинам вторая галера стала отставать и вскоре исчезла за горизонтом, а неизвестное судно, наоборот, увеличив скорость, приблизилось к первой галере. Но даже и тогда ее экипаж и охрана не заподозрили ничего плохого. И лишь разглядев чалмы на головах преследователей, поняли, что их настигли пираты. Поднялась суматоха, а тем временем пираты, осыпав галеру градом стрел, подтянули ее крюками к своему борту и бросились на абордаж. Нападение было столь стремительным, что за несколько минут охрана оказалась перебитой, а экипаж — плененным.
Казалось бы, можно было удовольствоваться этой добычей, но Арудж всегда был максималистом и не собирался упускать второй приз — отставшую галеру. В его голове возник хитроумный план. Приказав раздеть пленников, он загнал их в трюм, а в отобранную одежду обрядил своих пиратов. Затем все перешли на галеру и взяли собственное судно на буксир, имитируя, таким образом, полную победу папских воинов.
Вскоре показалась отставшая галера. Вид пиратского корабля, шедшего на буксире, вызвал у христиан прилив энтузиазма, и галера без всякой опаски подошла к борту «трофея». Тут-то Арудж и подал знак. В одну минуту роли поменялись, и вторая галера была захвачена столь же скоротечно, как и первая.
Эта победа еще более прославила имя Аруджа, но сам пират понимал, что без покровительства какого-либо владетеля его разбойные действия рано или поздно будут подавлены христианскими войсками. Поэтому после недолгого раздумья он обратился за помощью к эмиру Туниса. Само собой разумеется, эта помощь не могла быть оказана бесплатно, и после переговоров обе стороны пришли к компромиссу. Эмир отдавал во владение пиратов остров Джербу, за что получал двадцать процентов от пиратской добычи — сумму немалую, учитывая то обстоятельство, что удача не покидала Аруджа, из каждого грабительского похода он возвращался с богатыми трофеями.
