Не удовлетворив этим свою ненависть к испанцам и желая обезопасить свою столицу от повторения истории с Пеньоном, Барбаросса решил «наказать» этот клочок суши. Разгневанный Ксеркс приказал когда-то выпороть плетьми море, потопившее его корабли, Барбаросса повелел уничтожить остров. Но его нельзя было упрекнуть в необдуманности действий. По-видимому, Хайр-эд-Дин был начитанным человеком. Он знал историю о том, как Александр Македонский, будучи не в силах захватить островной город-крепость Тир, приказал превратить остров в полуостров. Александр сделал это до осады, Барбаросса осуществил это после, превзойдя великого Македонца.
Но ему была знакома и гавань Александрии - лучшая на Средиземном море. В этой гавани к острову Фарос, расположенному, как и Пеньон, на расстоянии окрика от берега, вела дамба, благодаря чему захват Александрии врасплох был делом невозможным. На следующий день после казни де Варгаса к северной части набережной Алжира напротив Пеньона были согнаны несколько тысяч рабов-христиан. В 1531 году остров перестал существовать, возведенный из камня полуостров двухсотметровой длины превратил Алжирскую бухту в лучшее пиратское убежище Западного Средиземноморья. Этот мол в Старой гавани Алжира до наших дней носит имя Хайр-эд-Дина.
«Ум и храбрость в нападении, прозорливость и отвага в обороне, огромная работоспособность, непобедимость - все эти похвальные качества заслонялись приливами неутомимой и холодной жестокости»,- писали о Хайр-эд-Дине в 1841 году авторы «Истории французского флота». Сумасбродство прекрасно уживалось в нем с осмотрительностью. Его покровитель Сулейман Великолепный вел в это время непрерывные войны в Европе, ему удалось захватить Белград, завоевать почти всю Венгрию, зеленое знамя пророка взвилось над большинством островов Эгейского моря, в Триполитании и Ираке. Над империей Карла, где «никогда не заходит солнце», неумолимо всходил полумесяц.
В 1528 году, когда турки выступили на Вену, Карл сумел переманить к себе талантливого итальянского адмирала-авантюриста Андреа Дориа, служившего до того французскому королю Франциску I.
Дориа и Барбаросса - долгие годы эти двое стояли лицом к лицу на рубеже двух миров. Это были достойные соперники. Пока флот Дориа щипал беззащитные острова Эгейского моря, утверждая эпизодически и ненадолго крест над полумесяцем, корабли Барбароссы терроризировали берега Италии. Узнав об этом, Дориа бросился на помощь родине, но в Мессинском проливе потерпел сокрушительное поражение и еле унес ноги в Венецию. Пираты преследовали его по пятам, открыв для себя при этом на много лет вперед богатые адриатические берега Италии.
Не удовлетворившись этой блистательной победой, Барбаросса в 1534 году на шестидесяти галерах вновь форсировал Мессинский пролив, захватил портовый город Реджо в Калабрии и прошелся по всему западному побережью Италии вплоть до Генуи, заполнив пленниками палубы и трюмы всех своих кораблей. (Об этом его рейде потом слагали легенды, иногда весьма пикантного содержания, где в числе персонажей можно найти красавицу-вдову и ее молодого слугу, а сюжетное действие сопровождается бешеной ночной скачкой молодой княгини через лес и «кровавой оргией» разочарованных пиратов. Все это, скорее всего, именно легенды, хотя доля истины в них может быть.)
В следующем году он захватил город Тунис, чей бей Мулен Хасан, как доложили Барбароссе, был подкуплен Карлом V. Год спустя Андреа Дориа удалось отбить Тунис, но цена оказалась чрезмерно высокой: пока испанцы в поте лица трудились у стен тунисской столицы, эскадра пиратов совершила молниеносный рейд к Балеарским островам, разорила Менорку и захватила на ней шесть тысяч пленных. Хайр-эд-Дин почтительнейше преподнес их в дар турецкому султану.
Дориа, этот кондотьер, продававший свою шпагу тем, чей кошелек выглядел внушительней, официально числился адмиралом испанского флота, слыл национальным героем и пользовался всеми преимуществами полноправного гражданина. Барбароссу, даже в самые отчаянные моменты сохранявшего верность своему султану, везде преследовала слава вероотступника, разбойника и плебея. Преследовала на протяжении всех шестидесяти лет, когда он верой и правдой служил своему султану.
Чтобы восстановить справедливость, Сулейман 15 октября 1535 года пожаловал Хайр-эд-Дину фирман (указ), возводивший преданного слугу в достоинство капудан-паши (главнокомандующего османским флотом) и бейлербея (бея над беями, по европейским понятиям - вице-короля) Северной Африки.