Действительно, в августе 1518 г. вице-король Сицилии, собрав многочисленную армию, послал к пирату парламентера с требованием немедленно сдаться. Хайраддина не испугало это заявление. «Дети пророка не страшатся смерти… Господь сам сделается нашим судьей!» – таков был ответ самозванца. На этот раз Господь был на стороне пиратов. Действительно, когда через шесть месяцев 26 испанских кораблей с 400 000 солдат появились на горизонте, то северный ветер принес свирепую бурю и уничтожил испанскую армаду. Несколько дней алжирцы собирали поклажу, выброшенную штормом на берег. Тут были пушки и бочки с порохом, провизия и корабельные канаты – как раз то, в чем пираты остро нуждались. Пиратам даже достались несколько судов, выброшенных на берег. Воодушевленный победой над испанцами, Хайраддин размышлял, как ему покорить всю Северную Африку. Он обратился с письмом к турецкому султану Сулейману I с просьбой признать его владычество над Алжиром. С просьбой он отправил четыре корабля, наполненные подарками. Далее случилось невозможное – пират Хайраддин стал правителем огромного государства. Султан признал его как собственного вассала, присвоил ему титул паши и подтвердил его притязания на Алжир. Три дня в Алжире продолжался праздник.
Хайраддин решил продолжить свои завоевания. Присланные две тысячи турецких янычар лучшим образом подходили для этого. Прежде всего необходимо было бороться за трон с Ахмедом, который пользовался поддержкой у алжирских мавров. Когда эти силы объединились с равнинными племенами, то Барбаросса бежал из города и укрылся в Джиджели – пристанище пиратов. Здесь он, как обычно, снаряжает несколько кораблей и отправляется пиратствовать. Накопив достаточно средств, он приступает к выполнению задуманного – отвоеванию Алжира. Несмотря на ряд успехов на море, он не мог вернуть Алжир. Главным препятствием являлся форт на острове Пеньон, оккупированном испанцами и закрывавшим вход в алжирский порт. Но в 1529 г. после многих попыток и 16 суток непрерывных бомбардировок острова он все же сумел сломить сопротивление испанцев и завладеть фортом. Чтобы обезопасить себя от различных неприятностей, Барбаросса направил несколько тысяч пленных христиан для строительства огромной дамбы, и через пару лет остров превратился в полуостров.
После этого Хайраддин становится владыкой Алжира. В 1534 г. он приступом берет Тунис. Возмущенный король Испании Карл V посылает к берегам Туниса мощный флот и через год отбирает землю у пиратов. Но через несколько дней Хайраддин осадил испанцев и отбил Тунис. Султан Сулейман Великолепный по достоинству оценил победы пиратов и присвоил Барбароссе звание Великого адмирала турецкого флота и назначил его бейлербеем (беем над беями), то есть верховным правителем всей Северной Африки.
Теперь пираты стали полноправными хозяевами Средиземного моря. На благодатном острове Джерба, который теперь славится фешенебельными отелями, они основали свою колонию, комфортабельно обустроились, а из черепов убитых христиан соорудили башню, правда, до наших дней она не дошла. По данным историков, Хайраддин перебил в сражениях и сгноил на работах от 500 до 700 тысяч человек. Это соизмеримо с взрослым населением некоторых королевств Европы.
Пираты из различных частей Средиземноморья использовали Джербу в качестве убежища в зимний период, когда после тяжелых морских походов они хотели отдохнуть и подготовиться к новым операциям. Здесь они заводили новые знакомства, заводили семьи, строили дома. В случае неудачи разбойники уходили на Джербу и выжидали благого случая, чтобы вновь броситься за добычей. В разное время здесь находились Аруджа, Хайраддин, Драгут и другие именитые пираты. Федеральные правители и местное население относились к пиратам дружественно. Кроме торговой пошлины в размере 80 000 золотых дукатов они получали от них награбленные товары по низким ценам.