После смерти короля Фердинанда в 1516 году жители Алжира восстали против испанской оккупации. Восстание возглавил араб Селим ат-Туми, который и стал алжирским эмиром. Испанский гарнизон перешел на островок у входа в гавань в форт Пеньон, где дон Мартин де Варгас с гарнизоном всего из полутысячи солдат стал ожидать помощи с моря или по суше из Орана. Муфтии посоветовали Селиму ат-Туми позвать на помощь Барбароссу.
Предвидя перемены в Алжире, Арудж и Xайр-эд-Дин заблаговременно перевели пиратские корабли с Джербы у берегов Туниса на скалистый алжирский архипелаг Агелли. Поэтому получив приглашение, Арудж послал брату приказ немедленно направиться к Алжиру со всем пиратским войском. А сам с 60 бойцами пошел туда же из Джиджелли.
Прибыв в Алжир, Арудж дождался быстрого прибытия брата со всеми пиратскими кораблями, удавил Селима и провозгласил себя правителем Алжира, начав даже чеканить собственную монету со своим профилем на ней. Барбаросса обложил высокими налогами город и окрестных племенных вождей, даже более высокими, чем взимали испанцы. Против новоявленного тирана составился заговор. Но среди заговорщиков нашелся предатель, ренегат (бывший христианин). Он и выдал заговорщиков Аруджу, который в ближайшую пятницу призвал их на пятничную молитву в главную мечеть, а заодно пригласил туда и богатейших горожан. Едва приглашенные на молитву вошли в мечеть и расстелили молитвенные коврики, как приближенные Аруджа – турки – заперли все двери, бросились на молившихся и порубили их саблями. Затем по приказу Аруджа обезглавленные тела были привязаны к хвостам ишаков, их проволокли по улицам города и сбросили в яму с нечистотами.
Муллы не осмелились осудить подобное святотатство. Барбаросса укрепился в Алжире, но захватить Пеньон и полностью открыть гавань Алжира, своей столицы, не смог. Но и испанский губернатор Орана не решался послать отряд в помощь осажденным на Пеньоне через районы проживания враждебных испанцам племен.
Барбаросса решил расширить границы своих владений на суше. В Алжир поступили сведения о смерти султана, правящего в богатом городе Тлемсене, расположенном примерно в 100 километрах южнее Орана. Это был крупный город, где имелось 12 тысяч домов, множество мечетей и бань. В его караван-сараях останавливалось немалое число купцов из Черной Африки. В гавани были склады и гостиницы генуэзских купцов. В одном из кварталов жили иудеи, бежавшие из Испании, среди них были богатые менялы и ростовщики, с которых султан взимал высокие налоги. В городе началась кровавая борьба за власть среди родственников умершего султана. Племянник посадил в тюрьму своего дядю Абу-Зайана, законного наследника, и отправил королю Испании Карлу I послание, в котором признавал себя его вассалом.
Барбаросса во главе отряда воинов направился в Тлемсен, оставив в Алжире брата. Сторонники арестованного Абу-Зайана открыли Барбароссе ворота города, так как он поклялся вызволить из тюрьмы законного султана и наказать узурпатора. Последний все же успел бежать в Оран под защиту испанского губернатора. Барбаросса освободил Абу-Зайана и тут же приказал повесить его. Так же беспощадно он расправился с семью сыновьями законного султана, а чтобы в зародыше подавить всякое сопротивление местной знати, он обезглавил 70 человек.
Но испанцы не стали мириться с новоявленным султаном Тлемсена. Сторонники бежавшего к испанцам племянника открыли ворота города, и испанцы во главе с губернатором Орана ворвались в город. Барбароссе со своим отрядом пришлось бежать из Тлемсена. По преданию, при бегстве, чтобы отвлечь преследователей, Барбаросса разбрасывал по дороге золото и серебро. Тем не менее он был застигнут на берегу реки Саладо, быстрое течение которой не позволило ему переправиться и уйти от погони. С остатками своего отряда Барбаросса укрылся за глинобитными стенами козьего загона и яростно отбивался от наседавших врагов, но был пригвожден копьем к стене сарая. Это случилось в мае 1518 году, видимо, на 44-м году жизни Аруджа Барбароссы.
По другой версии обстоятельств смерти Барбароссы I, ему удалось переправиться на другой берег реки, с которого он наблюдал безнадежную борьбу своего арьергарда, прикрывавшего отступление. Потрясенный героизмом и верностью своих воинов, он с ближайшими соратниками вновь переправился через реку и погиб в схватке с наседавшими испанцами.
Командир испанского отряда дон Гарсиа де Тинео отрубил голову еще дышавшему пирату. С тела погибшего пирата сняли серебряный протез руки. Голову с рыжей бородой насадили на древко штандарта, который отправили в Испанию и там возили из города в город, чтобы все убедились в гибели этого страшного врага испанской короны и всего христианского мира.