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

За своё предательство Мулей-бен-Хамид получил назад корону Тлемсена с обязательством выплачивать испанцам ежегодную дань и признать себя вассалом Испанского королевства.

На время Испания вздохнула с облегчением, но как оказалось, это был лишь первый акт трагедии и очень скоро место погибшего занял его брат — Хайреддин.

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

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

Поскольку собственных сил для удержания власти у него явно не хватало, он поступил вполне предсказуемо — в Константинополь был отправлен гонец, который от имени Хайреддина запросил помощи у султана, объявляя себя покорным слугой империи. Султан Селим, недавно закончивший завоевание Египта и стремившийся распространить своё влияние дальше на запад, с готовностью откликнулся на просьбу новоявленного вассала. Хайреддин был немедленно назначен бейлербеем Алжира. В придачу Селим направил на помощь своему новому подчинённому знаки его власти в виде ятагана, лошади и личного бунчука, а в качестве военной помощи — две тысячи янычар. Последние должны были стать надёжной опорой Хайреддина и позволили бы ему расширить свои владения. Их помощь оказалась весьма полезна, и в декабре 1518 года с их помощью он отвоевал Тлемсен, а затем в начале 1519 года — Бону.

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

Обезопасив себя, Хайреддин начал то, что у него получалось лучше всего — он занялся морским разбоем Имея 18 быстроходных галеотов, он несколько раз выходил в море на промысел, всякий раз возвращаясь с крупной добычей. Вскоре его слава разнеслась по всему Средиземному морю от Гибралтара до Леванта.

Уже в 1519 году Хайреддин совершил рейд по побережью Прованса. В 1521 году печальная участь постигла Балеарские острова, а затем он захватил несколько испанских кораблей, идущих с сокровищами Нового Света в Кадис. В качестве вассала султана он отправил в 1522 году часть своих сил на помощь турецкой армии, осаждавшей рыцарей ордена св. Иоана на Родосе.

После небольшой передышки и перегруппировки сил Хайреддин в 1525 году разграбил побережье острова Сардинии, а весной следующего года объявился в порту Кротон в Калабрии. Два стоявших в гавани испанских судна были пущены ко дну, а город разграблен. Не удовлетворившись этим в июне 1526 года, он прошёлся о гнём и мечом по побережью Тосканы. Однако после появления превосходящего по силе флота под командованием Андреа Дориа был вынужден спешно сменить место разбоя. Его новой жертвой в июле того же года стала Мессина и побережье Кампании.

Вероятно, размер полученной прибыли был впечатляющим, поскольку и в 1527 году Барбаросса продолжал рейды по побережью Италии и Испании.

Успех Хайреддина можно объяснить во многом тем, что в его подчинении оказались талантливые капитаны, ставшие впоследствии известными морскими разбойниками — Драгут, Салих, Синан по прозвищу «Еврей из Смирны», Айдин-раис, прозваванный испанцами «Каха дьяболо» («Бич дьявола»).

Каждый год, в период с мая по октябрь, алжирские пираты охотились на христианские корабли и нападали на прибрежные посёлки, пока зимние штормы не загоняли их обратно в порт. Некоторые пираты выходили даже за Геркулесовы столбы [1] и охотились на корабли, идущие из Америки в Кадис с грузом золота и серебра.

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

В 1529 году Хайреддин отправил Айдин-раиса и Салих-раиса во главе четырнадцати галиотов на Майорку. Эта парочка захватила несколько христианских кораблей, а затем разорила острова и испанское побережье. О появлении алжирских пиратов стало известно испанским морискам, [2] которые изъявили желание покинуть родину и переселиться в Северную Африку. В одну из ночей «Бич дьявола» прибыл в залив Олива, где принял на борт две сотни семей морисков с их сокровищами.