Заключив договор с эмиром Туниса, Арудж получил в распоряжение остров Джербу, на котором организовал базу своего пиратского флота, в обмен на обязательство отдавать эмиру 20 % захваченной пиратской добычи, однако вскоре сумел добиться уменьшения доли эмира до 10 % Пиратский флот Аруджа, пополняемый кроме турок и маврами, бежавшими из освобождённой христианами Испании, терроризировал все порты Средиземноморского побережья. В 1516 году мелкий мавританский султан Селим ат-Туми, призвав на помощь Аруджа, захватил Алжир и провозгласил себя эмиром Алжира. Пользовавшийся полным доверием нового эмира, Арудж, войдя к нему в бассейн во время купания, собственноручно задушил в воде Селима и провозгласил себя владыкой Алжира под именем Барбароссы I. В 1516—1517 годах Арудж разгромил войска Мулая Абу Абдаллаха, вассала испанского короля, взяв Медею, Тенес и другие поселения.
После ряда осложнений на суше и на море с войсками и флотом испанского короля Карла V султан Барбаросса I, потеряв значительное количество соратников, был вынужден оставить Алжир на своего брата Хайр-ад-Дина и с отрядом всего в 1500 человек отправиться за помощью к марокканскому султану. Настигнутый испанцами у реки Саладо, Барбаросса успел переправиться на другой берег и имел возможность спастись, однако, видя, как отважно сражаются его товарищи, принял решение вернуться к отряду и погиб в неравном бою.
Распространено мнение, что Арудж имел прозвище Барбаросса (то есть «Рыжебородый»). Однако в «Британской энциклопедии» сказано:
Вероятно, Аруджа при жизни не называли Рыжебородым. По всей видимости, это прозвище дали ему более поздние авторы.
В XX веке именем Аруджа было названо несколько подводных лодок ВМФ Турции (субмарины класса «Арудж Раис»).