17 августа 1518 года недалеко от алжирской столицы появился испанский флот под командованием Уго де Монкады. Последний отправил к Хайраддину парламентера с предложением сдать город, угрожая в случае неповиновения жестокой расправой. Рыжебородый ответил ему презрительным отказом. В тот же вечер Монкада высадился на берег с 1500 солдатами и расположился лагерем на холме. Шесть дней прошли в совершенном бездействии, а затем на море разыгрался шторм, выбросивший на берег 26 испанских судов. Хайраддин тут же атаковал неприятельский лагерь. Монкада, неся большие потери, отступил на уцелевшие корабли. Множество испанских солдат попали в плен и позже были казнены.
В том же году Хайраддин просил турецкого султана Селима I принять Алжир под свое покровительство. Получив от Селима I военную помощь и звание бейлербея, он укрепил свой авторитет, однако измена некоторых феодальных правителей заставила его в 1519 году оставить Алжир и уйти в порт Джиджели, а затем на Джербу. Начав войну на море против султана Туниса, Хайраддин весной 1520 года отправил корсаров к берегам Ифрикийи, где они захватили несколько тунисских судов. Вскоре 9 кораблей тунисских арматоров добровольно присоединились к флоту Барбароссы, вдвое усилив его боевую мощь.
Один из биографов так описывал внешность Хайраддина: «У него были лохматые брови, густая борода и толстый нос. Его толстая нижняя губа пренебрежительно выступала вперед. Он был среднего роста, однако обладал богатырской силой. На вытянутой руке он мог держать двухгодовалую овцу до тех пор, пока та не погибала… Поистине необычайное влияние, оказываемое им на своих командиров и простых пиратов, поклонники его объясняют огромной храбростью и ловкостью этого человека, а также тем, что даже самые отчаянные его предприятия всегда оканчивались успехом».
В 1521 году Хайраддин со своими корсарами появился в Джиджели, где авантюристы всех мастей толпами стекались под его знамена. В том же году он захватил город Колло, а в 1522 году – Аннабу и Константину. Не встречая сопротивления, Хайраддин 1525 году вступил в город Алжир, где был с ликованием встречен своими приверженцами. Столь же легко он овладел Тенесом и Шершелем. В начале 1529 года почти вся территория Алжира оказалась под властью Рыжебородого.
6 мая он приступил к осаде островной крепости Пеньон д’Архель, блокировавшей столицу со стороны моря. Пеньон отвечал градом пуль и ядер. В городе начались пожары. Подавив большинство испанских батарей, Хайраддин 27 мая бросил своих воинов на решающий приступ. С моря их поддерживали огнем 45 кораблей. Через несколько часов Пеньон д’Архель был взят, а его гарнизон полностью истреблен. По приказу Барбаросcы коменданта крепости изрубили на куски и выбросили в море; развалины укреплений были срыты и сровнены с землей.
В 1529—1532 годах испанский флот совершил несколько неудачных нападений на Шершель, Хунейн и другие базы алжирских корсаров. Хайраддин в свою очередь совершил 7 рейдов к берегам Испании и спас 70 тыс. морисков.
В 1533 году турецкий султан Сулейман II пригласил Хайраддина в Стамбул. В середине августа он вышел из Алжира с 18 кораблями, по пути присоединил к своей флотилии еще 16 корсарских судов, разорил остров Эльбу, захватил и частью сжег на широте Пьомбино 13 генуэзских галер и прибыл в Стамбул с 40 кораблями. Одарив султана богатыми подарками, он был назначен начальником арсенала, а 16 мая 1534 года получил из рук султана флаг великого адмирала (капудан-паши). Возглавив флот из 64 кораблей, он в начале августа опустошил прибрежные районы Италии, а 13 августа появился на рейде Бизерты. Войска и население этого тунисского города приветствовали турок, изгнав хафсидского каида.
15 августа 1534 года корабли Хайраддина подошли к Ла-Гулетте – морской крепости тунисской столицы. Гарнизон крепости тут же перешел на сторону турок. 16 августа Рыжебородый сошел на берег, объявил о низложении династии Хафсидов и переходе Туниса под власть Османской империи. 18 августа произошло решающее сражение за город Тунис. Весь город был усеян трупами. Погибло свыше 3000 тунисцев и около 400 янычар. Султан Мулай Хасан, не дожидаясь окончания резни, бежал. К вечеру Хайраддин велел прекратить кровопролитие.
При содействии великого магистра Мальтийского ордена Мулай Хасан связался с вице-королем Неаполя и по его совету попросил помощи у императора Священной Римской империи Карла V. 2 июня 1535 года флот Карла V отбыл из Барселоны. Армада, находившаяся под командованием Андреа Дориа, насчитывала около 400 кораблей, в том числе 90 боевых галер. Узнав о подготовке экспедиции против Туниса, Барбаросса начал укреплять город и порт. 12 лучших кораблей эскадры были поставлены на якоря перед Ла-Гулеттой. Устаревшие корабли были затоплены или вытащены на берег, а их пушки установлены в крепости и на валу.