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

Между тем Арудж, понимая, что необходимо сконцентрировать больше войск, продолжал накапливать силы, готовясь к решительному удару. Он отослал в Тунис послание своему брату Хайремину с просьбой собрать столько пиратов, сколько будет возможно, обещая большие деньги за службу. Хайремин с успехом выполнил задание и нанял три сотни лучших турецких и мавританских солдат, которых можно было найти на северо-африканском побережье. Этот отряд высадился на мысе Матифу и пешком направился в Алжир. Кроме того, представители окрестных берберских племён сочли делом чести выступить против испанцев и начали стягивать свои отряды к городу. Не прошло и месяца, как в подчинении у Аруджа оказался внушительный отряд из нескольких тысяч воинов.

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

После того как известие о смерти Селима достигло горожан, Арудж официально объявил, что причиной смерти правителя явился острый приступ его хронических болезней. Несмотря на то что очень немногие поверили этому, Арудж в один момент превратился в единовластного правителя Алжира.

Сын Селима, понимая, что если он предъявит претензии на престол, ему уготована такая же участь, предпочёл сбежать в Оран, где укрылся у испанского губернатора. Алжирская знать также не высказала удовольствия действиями пришельца. Несмотря на попытки привлечь их на свою сторону разными посулами и подарками, Арудж не достиг своей цели. Против узурпатора созрел заговор. Согласно замыслам заговорщиков, в назначенный день алжирцы должны были напасть на отряд Аруджа и перебить его, призвав на помощь гарнизон Пеньона. Только предательство раба-христианина, купившего себе таким образом свободу, спасло Аруджа от расправы. Он решил нанести упреждающий удар. В пятницу, после утренней молитвы, Арудж призвал к себе представителей городской знати, якобы для ведения переговоров. Когда почтенные горожане вошли в мечеть, турки закрыли все двери и набросились на безоружных горожан.

Изрубленные останки турецкие янычары протащили по всему городу, а потом сбросили в яму с нечистотами, показывая, какая участь ждёт всякого, кто посмеет перечить новым властям Урок оказался весьма полезным, и алжирцы предпочли затаить обиду и подчиниться силе.

Укрепив свою власть, Арудж был вынужден устранить ещё одну опасность. Узнав о перевороте в Алжире, испанцы решили искоренить существовавшую опасность. К городу была направлена эскадра под командованием Диего де Вера.

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

Потеря своей армии стоила де Веру не только королевской опалы, но и проклятий со стороны простых испанцев. Где бы он ни появлялся, его освистывали и забрасывали камнями, считая именно его главным виновником позорного поражения. В то же время Арудж пребывал на вершине популярности и начал активно возрождать пиратский флот.

Галеры алжирцев снова вышли в море на разбойный промысел. Кроме того, Арудж озаботился расширением своих владений. В 1517 году он овладел несколькими поселениями, распространяя свою власть вдоль североафриканского побережья.

Успехи вскружили голову Аруджу, и когда ему сообщили о том, что в Тлемсене началась междоусобная борьба за власть, новоявленный правитель Алжира с радостью воспринял идею расширить свои владения. Его главным противником стал Мулей-бен-Хамид, главный претендент на корону Тлемсена.

Собрав все наличные силы и дождавшись подкреплений из Алжира, Арудж двинул войска в пустыню. Встреча двух армий произошла в нескольких милях от Орана на обширной равнине. Турецкие янычары оказались решающей силой в бою. Профессиональные солдаты с лёгкостью отбили атаку арабской кавалерии, а обстрел из орудий довершил дело. Армия Мулей-бен-Хамида была разбита и бежала с поля боя.

Дорога на Тлемсен была открыта. Достигнув конечной цели, Арудж освободил из заключения и восстановил в правах «законного» наследника Мулей-бен-Заина. Однако этот благородный жест был не чем иным, как банальной уловкой ловкого политика, жаждущего расширения своих владений. Не прошло и дня, как турки заняли все ключевые точки города, городскую цитадель и все укрепления. После этого благородный фарс был уже не нужен, и Арудж приказал повесить новоявленного султана и семерых его сыновей. Остальные родственники были утоплены в бассейне. Таким образом, Арудж расчистил себе путь к единоличной власти над Тлемсеном.

Несколько месяцев армия Аруджа орудовала в городе, выискивая недовольных и предавая их смерти. Только спустя девять месяцев новоявленный султан внезапно заявил, что желает вернуться в Алжир. Для выборов нового султана он пригласил в свой дворец 70 наиболее знатных представителей Тлемсена. Однако, когда благородные горожане заняли свои места в зале собраний, Арудж приказал казнить их. Подлое убийство безоружных людей переполнило чашу терпения местных жителей, но они не отваживались на открытое выступление против тирана.

Завоёвывая Тлемсен, Арудж допустил лишь одну ошибку — не уничтожил Мулей-бен-Хамида. Между тем Хамид не терял времени даром и обратился за помощью к испанцам. Гарнизон Орана был достаточно многочисленным, но соседство армии Аруджа вызывало у коменданта справедливое опасение о судьбе ввереных ему креплений. В результате испанцы решили действовать более активно и смело. Прежде всего необходимо было пресечь поступление подкреплений из Алжира. Когда стало известно, что на помощь Аруджу идёт отряд их 600 турок, его перехватили у Эль-Кале и почти весь перебили.

Арудж оказался отрезан. Вокруг крепости расположились испанцы, внутри назревал бунт. Оставался лишь один путь к спасению — бегство. В мае 1518 года, собрав сотню наиболее преданных солдат, алжирский правитель решил пробиваться из окружения. Естественно, об этом тут же было доложено испанцам, и в погоню за ним устремился отряд испанской кавалерии. Несмотря на все уловки, которые использовал Арудж, чтобы сбить преследователей со следа, ему это не удалось. Он был настигнут и в коротком бою лишился жизни. Его отрубленную голову в качестве трофея испанцы отправили в Оран, а затем в Испанию.