Искусные хирурги, ампутировав Аруджу руку, сделали пиратскому вожаку серебряный протез на шарнирах, что позволило ему продолжить свою деятельность. Из Биджаи Арудж и Хызыр с 5 кораблями отправились в набег к побережью Андалусии, захватили галеот, принадлежавший известной генуэзской семье Ломеллини, а затем опустошили Минорку.

В 1513 году братья-корсары несколько раз успешно нападали на корабли христиан в водах Испании. В августе следующего года Арудж и Хызыр начали вторую осаду Биджаи. Десант, высаженный с 12 кораблей, был поддержан повстанцами с соседних гор. Они ворвались в город, взяли старую крепость и осадили новый испанский замок. Когда с Майорки прибыли испанские подкрепления, Арудж ушел в Сеуту (Марокко), разорил этот портовый город, а затем захватил алжирский город Жижель (совр. Джиджель), население которого перешло на его сторону. В Тунисе корсары овладели портом Махдия, затем опустошили прибрежные районы Сицилии, Сардинии, Балеарских островов и Испании, захватив там 3 больших судна. В 1515 году галеры Аруджа снова оперировали в районе Балеарских островов, где их призами стали несколько галеонов, 1 галера и 3 барка.

Решив заручиться поддержкой турецкого султана, братья отправили в Стамбул Пири Реиса – племянника Кемаля Реиса. Миссия Пири Реиса увенчалась успехом. Селим I (1512—1520) простил все прошлые «заблуждения» братьев, одарил их дорогими кафтанами с почетным оружием, украшенным бриллиантами, и прислал 2 галеры с военным снаряжением.

Широкий резонанс имело взятие Аруджем города Алжира. После смерти испанского короля Фердинанда V жители города отказались присягать на верность новому королю Карлосу I и обратились за помощью к Аруджу. Весной 1516 года его войска заняли Митиджу, Джиджель и вступили в Алжир. Однако ему не удалось взять островную крепость Пеньон д’Архель.

Когда Арудж предательски убил местного шейха Салема ат-Туми, корсары и повстанцы провозгласили своего главаря султаном, приказав чеканить его имя на алжирских монетах. Представителей знати, недовольных новыми порядками, Арудж пригласил на торжественное моление в главную мечеть. Там их и зарезали. Отрубленные головы «мятежников» были выставлены на улицах города. Укрепив свою власть в городе, Арудж принял меры по дальнейшему усилению обороны и усилил блокаду Пеньон д’Археля. В сентябре 1516 года испанская эскадра под командованием дона Диего де Веры подошла к Алжиру и высадила на берег более 3 тыс. солдат. Арудж во главе своих людей атаковал неприятеля. 4 октября в сражении на речке Уэд-эль-Харраш близ города Алжира испанский десант был разбит. По данным памплонского епископа Сандоваля, турки «убили 3000 человек и взяли в плен 400». Сам адмирал Диего де Вера едва унес ноги.

Зимой 1516—1517 годов Арудж разгромил войска владетеля Тенеса Мулая Абу Абдаллаха, вассала испанского короля, взяв Медею, Милиану, Тенес и другие поселения. Весной 1517 года он двинулся на столицу Абдальвадидов – город Тлемсен, в сражении под Сиди-Бель-Аббесом разбил 9 тысячную армию Абу Хамму III и вступил в Тлемсен, жители которого открыли ему ворота. Абу Хамму III бежал из города. Низложив династию Абдальвадидов, Арудж велел повесить на зубцах тлемсенской цитадели дядю свергнутого правителя, Абу Зайяна, а также 7 сыновей последнего и 70 эмиров царствующей фамилии.

Для укрепления своих позиций в Северной Африке Арудж решил отказаться от титула султана Алжира в пользу турецкого султана, на помощь которого он рассчитывал. Султан согласился принять Алжир в состав Османской империи в качестве отдельной провинции, назначив Аруджа беем Алжира и бейлербеем Западного Средиземноморья.