Такое положение вещей в конце концов побудило арагонского короля Фердинанда начать ответные действия против пиратов. Испанские экспедиционные войска захватили главные опорные пункты берберских пиратов, такие, как Алжир, Бужи, Оран. Города эти были разграблены и сожжены, а их жители обложены большой данью, что практически не позволяло им впредь оказывать материальную поддержку пиратам. Кроме того, чтобы преградить пиратским кораблям доступ к Алжиру с моря, испанцы построили мощную систему фортов на острове Пеньон, которая долгое время перечеркивала всякие желания пиратов вернуть себе Алжир.
Победа испанских войск подорвала авторитет Аруджа и подвигла его на необдуманные поступки. Так, в горячке он решил напасть на Бужи и одновременно — на испанский флот. То и другое кончилось для него полным провалом, и Аруджу пришлось смириться с пребыванием испанцев в Северной Африке. Он снова сосредоточил все свои усилия на грабеже судов в море.
Тем временем, в 1516 году, умер король Фердинанд, и этим тотчас воспользовалось население Алжира, которое подняло восстание против оккупационных войск. Его возглавил араб Салим, пригласивший к себе на помощь Аруджа с его пиратами. Алжир был атакован с моря и с суши и после ожесточенной борьбы взят. Оставшиеся в живых испанцы отошли к острову Пеньон, под защиту его фортов.
Таким образом, Алжир вновь перешел к арабам, и Салим провозгласил себя его эмиром. Но этот факт ни в коей мере не устраивал честолюбивого Аруджа. Ему и его пиратам принадлежала честь отвоевания Алжира у «неверных», и пиратский предводитель не собирался терпеть на эмирском троне никому не известного до сей поры Салима. А потому в один прекрасный день Арудж отправился во дворец нового эмира. Он застал его купающимся в бассейне и, не долго думая, задушил. Покончив с соперником, Арудж провозгласил себя правителем Алжира и присвоил себе титул — султан Барбаросса. Но, поскольку этим же именем должен был называться и брат Аруджа Ацор, то историки во избежание путаницы присвоили братьям порядковые номера — Арудж стал Барбароссой I, Ацор — Барбароссой II.
Итак, султан Арудж стал одним из богатейших людей Североафриканского побережья. Казалось бы, есть все основания укрепить свое влияние и возглавить борьбу против испанцев, под властью которых оставались некоторые арабские города.
Но случилось обратное. Арудж показал себя в Алжире не мудрым правителем, а жестоким тираном, чем вызвал недовольство жителей, которое вскоре переросло в восстание и осложнилось новой военной экспедицией испанцев. Их предводитель, маркиз де Комарес, захватил город, и Аруджу пришлось бежать. С ним было всего полторы тысячи пиратов, тогда как испанские войска насчитывали десять тысяч человек. Они преследовали Аруджа по пятам, тем более что их воодушевлял слух, будто пиратский вождь захватил с собой все свои несметные сокровища. Так это или не так, никто не знает, однако легенда утверждает, что на всем пути отступления Арудж, дабы задержать преследователей, разбрасывал серебро и золото. Но это не помогло, и Арудж погиб вместе с верными ему пиратами.
Гибель Аруджа описывают по-разному. Ф. Архенгольц, автор «Истории морских разбойников Средиземного моря и Океана», утверждает: "после тридцатичасового преследования испанцы настигают его в небольшой пустыне, прилегающей к марокканскому городку Дубуду. Утомленный усталостью и жаждой, султан алжирский с горстью уцелевших товарищей укрылся в небольшом козьем парке, огражденном низкой стеной, сложенной из камня без цоколя. Окруженный со всех сторон, он обороняется как раненый лев, пригвожденный к земле копьем, он все еще защищается, пока испанский знаменосец дон Гарсиа де Тинео не отрубил ему головы. Голова его, воткнутая на знамя, была отправлена в Оран, а оттуда в Испанию. В Кордове, в монастыре Святого Иеронима, до сих пор еще показывают камзол его из малинового бархата, шитый золотом.
Таков был, в мае 1518 года, на зб году от роду, после 14 лет бродячей жизни и двадцатимесячного царствования, конец страшного Харуджи, известного в новейших летописях под именем Барбароссы".
Современный знаток истории пиратства, поляк Яцек Маховский, дает свою версию смерти Аруджа: "Испанские солдаты, прельщенные перспективой богатой добычи, слухами о фантастических сокровищах, унесенных пиратами из Алжира, преследовали Барбароссу до самой реки Саладо.
Аруджу удалось переправиться на другой берег, с которого он наблюдал безнадежную борьбу своего арьергарда, прикрывавшего отступление. Глубоко тронутый героизмом и верностью своих товарищей, он решил поспешить им на помощь. Вновь переправившись со свитой через реку, Барбаросса присоединился к защитникам плацдарма. При этом он прекрасно осознавал всю безнадежность положения.
Через несколько часов победоносные испанцы обнаружили на поле боя изувеченный труп Барбароссы".
Как бы там ни было, но факт оставался фактом погиб человек, имя которого на протяжении долгого времени наводило ужас на прибрежные города Средиземного моря. Узнав об этом, христианская Европа вздохнула свободно.