Очевидно, ещё до своего пленения Арудж был тесно связан с принцем Шехзаде Коркудом, одним из сыновей султана Баязида II; полагают, что именно этот принц выкупил его из плена. Прибыв в Анталью, находившуюся под управлением Коркуда, Арудж принял под своё командование 18 галер и развернул морские операции против родосских рыцарей. В последующие годы, когда Коркуд стал правителем Манисы, он передал Аруджу 24 галеры и приказал ему совершить набег на побережье Апулии; там корсары бомбардировали прибрежные крепости и захватили 2 судна. На обратном пути Арудж зашёл на Эвбею, где овладел 3 галеонами и ещё одним кораблём. Приведя свои призы на Лесбос, он узнал, что Коркуд, будучи братом нового турецкого султана, вынужден был бежать в Египет. Туда же отправился и Арудж. Коркуд помог ему добиться аудиенции у мамлюкского султана, который позволил корсару грабить суда христиан. В 1503 г. Арудж руководил захватом 3 больших кораблей и тогда же сделал своей базой о. Джерба. Там к нему присоединился его брат Хызыр. В 1504 г. братья добились от султана Туниса разрешения базироваться в Ла-Гулетте, отдавая ему Уз часть добычи. Командуя небольшими галиотами, Арудж прославился захватом близ Эльбы 2 галер, принадлежавших римскому папе. Позже в районе Липарских о-вов он взял корабль «Кавалерия», на борту которого находились 380 испанских солдат и 60 мальтийских рыцарей.
В 1509 г. в Ла-Гулетт прибыл Исхак, присоединившийся к Аруджу и Хызыру. В 1510 г. братья разорили окрестности мыса Пассеро в Сицилии и отбили испанские атаки на Биджаю, Оран и Алжир. В конце июля того же года нападению со стороны испанцев подверглась Джерба: 8 галер под командованием графа Педро де Наварро блокировали подходы к острову. Но правитель Джербы отказался капитулировать. Парламентёры графа были убиты. Сняв осаду, он отступил в Триполи, где подготовил новую экспедицию. На борт 120 судов поднялись 15 тыс. солдат. 23 августа испанская армада появилась в виду Джербы, а 30 августа началась высадка войск на берег. Арудж принял участие в обороне острова. Испанский авангард был полностью уничтожен. В довершение ко всему разразился шторм, во время которого 18 испанских судов были выброшены на берег.
К 1512 г. у Аруджа и Хызыра на Джербе было уже 12 боевых галер и 1 тыс. корсаров. Противодействуя испанской экспансии в Магрибе, Арудж в августе 1512 г. высадился в районе Биджаи и атаковал находившийся там испанский гарнизон. К нему тотчас присоединились 4 тыс. повстанцев. На восьмой день, пробив брешь в крепостной стене, корсары и повстанцы пошли на приступ, но в этот момент Арудж был ранен ядром в руку. Среди мусульман началось смятение, и они отступили. Из Биджаи Арудж и Хызыр отправились в набег к берегам Андалусии, а затем опустошили Менорку. В 1513 г. братья-корсары несколько раз нападали на корабли христиан в водах Испании. В августе 1514г. Арудж и Хызыр начали вторую осаду Биджаи. Десант, высаженный с кораблей, был под держан повстанцами с гор. Они ворвались в город, взяли старую крепость и осадили новый замок. Когда с Майорки прибыли испанские подкрепления, Арудж ушёл в Сеуту, разорил её, а затем захватил алжирский город Джиджель. В Тунисе корсары овладели Махдией, затем опустошили прибрежные районы Сицилии, Сардинии, Балеарских о-вов и Испании. В 1515г. галеры Аруджа снова оперировали в районе Балеарских о-вов.
Решив заручиться поддержкой турецкого султана, братья отправили в Стамбул Пири Рейса. Его миссия увенчалась успехом. Селим I простил все прошлые «заблуждения» братьев, одарил их кафтанами с почётным оружием и прислал 2 галеры с военным снаряжением.
Широкий резонанс имело взятие Аруджем города Алжира. После смерти испанского короля Фердинанда V жители города отказались присягать на верность новому королю Карлосу I и обратились за помощью к Аруджу. Весной 1516 г. его войска заняли Митиджу, Джиджель и вступили в Алжир. Однако ему не удалось взять крепость Пеньон д’Архель. Когда Арудж предательски убил местного шейха Салема ат-Туми, корсары и повстанцы провозгласили своего главаря султаном, приказав чеканить его имя на монетах. Представителей знати, недовольных новыми порядками, Арудж пригласил на моление в главную мечеть. Там их и зарезали. Отрубленные головы «мятежников» были выставлены на улицах города. Укрепив свою власть в городе, Арудж принял меры по укреплению обороны и усилил блокаду Пеньон д’Археля. В сентябре испанская эскадра под командованием Диего де Веры подошла к Алжиру и высадила на берег более 3 тыс. солдат. Арудж во главе своих людей атаковал неприятеля; испанский десант был разбит. По данным епископа Сандоваля, турки «убили 3000 человек и взяли в плен 400». Сам адмирал Диего де Вера едва унёс ноги.