17 августа 1518 года недалеко от алжирской столицы появился испанский флот под командованием Уго де Монкады. Последний отправил к Хайраддину парламентера с предложением сдать город, угрожая в случае неповиновения жестокой расправой. Рыжебородый ответил ему презрительным отказом. В тот же вечер Монкада высадился на берег с 1500 солдатами и расположился лагерем на холме. Шесть дней прошли в совершенном бездействии, а затем на море разыгрался шторм, выбросивший на берег 26 испанских судов. Хайраддин тут же атаковал неприятельский лагерь. Монкада, неся большие потери, отступил на уцелевшие корабли. Множество испанских солдат попали в плен и позже были казнены.
В том же году Хайраддин просил турецкого султана Селима I принять Алжир под свое покровительство. Получив от Селима I военную помощь и звание бейлербея, он укрепил свой авторитет, однако измена некоторых феодальных правителей заставила его в 1519 году оставить Алжир и уйти в порт Джиджели, а затем на Джербу. Начав войну на море против султана Туниса, Хайраддин весной 1520 года отправил корсаров к берегам Ифрикийи, где они захватили несколько тунисских судов. Вскоре 9 кораблей тунисских арматоров добровольно присоединились к флоту Барбароссы, вдвое усилив его боевую мощь.
Один из биографов так описывал внешность Хайраддина: «У него были лохматые брови, густая борода и толстый нос. Его толстая нижняя губа пренебрежительно выступала вперед. Он был среднего роста, однако обладал богатырской силой. На вытянутой руке он мог держать двухгодовалую овцу до тех пор, пока та не погибала… Поистине необычайное влияние, оказываемое им на своих командиров и простых пиратов, поклонники его объясняют огромной храбростью и ловкостью этого человека, а также тем, что даже самые отчаянные его предприятия всегда оканчивались успехом».
В 1521 году Хайраддин со своими корсарами появился в Джиджели, где авантюристы всех мастей толпами стекались под его знамена. В том же году он захватил город Колло, а в 1522 году – Аннабу и Константину. Не встречая сопротивления, Хайраддин 1525 году вступил в город Алжир, где был с ликованием встречен своими приверженцами. Столь же легко он овладел Тенесом и Шершелем. В начале 1529 года почти вся территория Алжира оказалась под властью Рыжебородого.
6 мая он приступил к осаде островной крепости Пеньон д’Архель, блокировавшей столицу со стороны моря. Пеньон отвечал градом пуль и ядер. В городе начались пожары. Подавив большинство испанских батарей, Хайраддин 27 мая бросил своих воинов на решающий приступ. С моря их поддерживали огнем 45 кораблей. Через несколько часов Пеньон д’Архель был взят, а его гарнизон полностью истреблен. По приказу Барбаросcы коменданта крепости изрубили на куски и выбросили в море; развалины укреплений были срыты и сровнены с землей.