Поражение брата поставило его в затруднительное положение. Жители Тенеса, Шершеля и Алжира, кабилы Куко, сторонника свергнутого государя Тлемсена, — все стремились освободиться от власти корсаров. Тогда Хайраддин принял гениальное решение и связал свою судьбу с Османской империей. Один он был бы раздавлен своими многочисленными врагами; опираясь же на поддержку Порты, он поднимал свой престиж и получал военную и финансовую помощь, которая дала бы ему возможность осуществить обширные замыслы. Поэтому он поспешил принести клятву верности султану Селиму, который дал ему титул паши и назначил эмиром эмиров (бейлербей). Более того, он получил из Константинополя 2 тысячи человек с артиллерией, затем еще 4 тысячи волонтеров, занявших привилегированное положение янычаров.
Эти подкрепления прибыли вовремя, чтобы предотвратить серьезные опасности: заговор алжирцев и племен, который был потоплен в крови, а также новый натиск испанцев под командованием Уго де Монкады, закончившийся полным провалом (1519 год). Но вследствие предательства войск Куко на поле боя он был разбит в Кабилии хафсидской армией и вынужден даже покинуть Алжир, чтобы укрыться в Джиджелли, где вернулся к карьере корсара (1520–1525 годы).
Тем не менее он отнюдь не отказался от своих честолюбивых устремлений. Восстановив свою армию и пополнив казну, Хайраддин захватил Колло (1521 год), Бон (1522 год) и Константину; затем с помощью султана из рода Бану Аббас изгнал из Алжира кабилов Куко, которые не пользовались там популярностью, и занял Митиджу (1525 год). Подавление нескольких восстаний в Кабилии и Ходне, в Шершеле, Тенесе и Константине заставило туземцев почувствовать, что их новый повелитель не знает жалости.
Оставалась крепость Пеньон, угроза которой по-прежнему висела над Алжиром. Хайраддин решил предпринять против нее мощную атаку. После трехнедельной бомбардировки комендант Мартин де Варгас, у которого от 150 человек осталось только 25 и который ниоткуда не ждал помощи, сдал крепость и умер под палками (27 мая 1529 года). Хайраддин немедленно приказал срыть внешний пояс ее укреплений.
Алжир представлял в то время незавидную гавань, Усеянную подводными камнями и открытую ветрам. Корсары были вынуждены вытягивать свои суда на пляж Баб аль-Уэда, находившийся тогда в одной миле от города. Хайраддин распорядился, чтобы из остатков крепости Пеньон и развалин Русгуний (Матифу) пленные христиане построили мол длиной 200 м, шириной 25 м и высотой 4 м, который соединил город с островками. Так был создан порт Алжира. Хотя позже он был защищен еще одним молом с юго-востока (Большой мол), он оставался все же посредственным укрытием, не защищенным от волнения при восточных и северо-западных ветрах, по его положение между Сицилийским проливом и входом в западное Средиземноморье позволяло «следить за кратчайшими путями из Гибралтара в восточное Средиземноморье, из южной Испании на юг Италии или в Сицилию и перекрывать их» (Леспес). Поэтому турки превратили военный порт, положение которого было куда важнее, чем значение его как якорной стоянки, в укрепленную базу и укрытие для своего флота. Оккупация Бужи и Орана испанцами, которые уничтожили там пиратские гнезда, позволила Алжиру Хайраддина монополизировать пиратский промысел в Среднем Магрибе.
Завоевание Туниса.
Владея Алжиром, Хайраддин хотел получить в свое полное распоряжение также и восточное побережье. Воспользовавшись раздорами при хафсидском дворе и недовольством населения своим султаном Мулай Хасаном, он при поддержке Порты совершил нападение на Тунис. Хорошо принятые в Бизерте, затем в Ла-Гулете, где они предстали как сторонники одного из претендентов на власть, турки вступили в столицу после недолгого боя (18 августа 1534 года). Разграбив город, Барбаросса прокламировал низложение Хафсидов и общую амнистию. Он разместил гарнизон в Кайруане, без особого труда присоединил города побережья и даже добился содействия могущественных племен южной Константины.Организация турками морского разбоя в Тунисе непосредственно угрожала папе и итальянским князьям. Она совпала- с возрождением в Европе духа крестовых походов и с возникновением персидской угрозы, отвлекавшей внимание Константинополя на восток. Лишившись союзников, король Франции Франциск I обещал свой нейтралитет в случае, если его враг Карл V выступит против варварийцев. Император колебался, направить ли ему свои усилия на Алжир или на Тунис. Быть может, призывы свергнутого султана Мулай Хасана и, главное, желание изолировать Алжир от Константинополя склонили его в пользу хафсидской столицы. Флот из 400 судов с 30 тысячами человек беспрепятственно подошел к Карфагену. Испанцы заняли Ла-Гулет (14 июля 1535 года), а через шесть дней Тунис, где христианские рабы, которых Барбаросса не пожелал уничтожить, разбили оковы и захватили касбу.