Сулейман I был в гневе на Люфти-пашу за проявленную нерешительность и приказал вызвать из Алжира Хайреддина Барбароссу.
В 1533 году тот по приглашению султана прибыл в Стамбул со своим флотом из 18 галер. Его корабли привезли подарки для султана, в том числе рабов. Среди подарков были золотые украшения и слитки, драгоценные камни и дорогие ткани, а также верблюды, львы и другие африканские животные, а также большая группа молодых христианских женщин. В ответ султан щедро одарил пирата и назначил его командующим всем турецким флотом в Северной Африке и одновременно бейлербеем Африки. С этого дня не только флот, но и все беи африканских провинций Османской империи подчинялись Барбароссе.
Сулейман также назначил Барбароссу капудан-пашой, то есть главным адмиралом, и предоставил в его полное распоряжение арсенал в Галатеи, верфи в Стамбуле и Измире. Капудан-паша (капудан-и дерья) из своей резиденции в арсенале Касим-паши в Стамбуле руководил всеми моряками и всеми начальниками и рабочими арсеналов, строившими корабли и орудия для них.
Получив задание султана «показать свое умение в строительстве кораблей», Барбаросса вместе со своими людьми направился на стамбульские верфи, чтобы осуществлять надзор, ускорить строительство и давать советы, какие именно корабли надо строить. Благодаря усилиям адмирала морская мощь Османской империи стала ощутимой во всем Средиземноморье и под контроль империи перешла большая часть североафриканского побережья.
Получив от султана почетное звание «Хранитель веры», Хайреддин Барбаросса стал весьма религиозным человеком, начал соблюдать все мусульманские обряды и требовал того же от своих подчиненных, что отнюдь не вызывало у них энтузиазма. Барбаросса уверовал, что именно Аллах дарует ему победу в сражениях. К нему присоединялись и некоторые европейские моряки, устраивавшие бунт на своих судах из-за плохого питания и мизерного жалованья.
Между прочим, на зеленом флаге Барбароссы была изображена Звезда Давида. В исламе она была символом печати Соломона и означала мудрость, власть над джиннами, возможность разговаривать с животными и вообще власть над любыми стихиями, в том числе морской.
Барбаросса теперь строил корабли в Стамбуле и Измире. Он установил жесткие правила поведения на кораблях. Запретить морякам пить совсем было делом безнадежным. Адмирал потребовал лишь, чтобы матросы не напивались пьяными, а в бой непременно шли трезвыми. А вот играть в карты и кости на деньги на кораблях было абсолютно запрещено, поскольку это разлагало экипажи и нередко приводило к поножовщине. Нарушителей жестко карали. Хайреддин требовал содержать оружие в чистоте и порядке, иначе грозил лишить моряков их доли добычи.
На портрете Барбароссы, сохранившемся в турецких архивах, изображен человек с лохматыми бровями, густой бородой, толстым носом и толстой нижней губой, выступающей вперед. Что называется, раскатал губы! Капудан-паша был среднего роста, но при этом невероятно силен. По преданию, на вытянутой руке он выдерживал двухгодовалую овцу до тех пор, пока та не погибала.
Командующий христианским флотом и главный противник турецкого адмирала генуэзский адмирал Андреа Дориа, служивший императору Карлу V, пытался вызвать Барбароссу на бой, но тот умело уклонялся от сражения в невыгодных условиях.
По отношению к христианам Хайреддин проявлял необычайную жестокость, пленных безжалостно казнил, выставляя отрубленные головы на всеобщее обозрение.
В то же время Барбаросса был суеверен и носил на шее оберег в форме глаза, подаренный Сулейманом. Он никогда не брал на корабли женщин, но не только из суеверия, а еще и потому, что понимал: присутствие женщин на борту основательно подорвет дисциплину его не слишком добродетельного воинства.
В июле 1534 года флот Барбароссы, насчитывавший 84 галеры, вышел из Дарданелл. Барбаросса решил продвигаться в западном направлении, чтобы опустошить побережья и порты Италии вдоль Мессинского пролива и севернее, во владениях Неаполитанского королевства. С частью кораблей капудан-паша прошел Мессинский пролив, разграбил города области Реджо-ди-Калабрия, захватив в Четраро 18 венецианских галер и высадив турецкие десанты по итальянскому побережью вплоть до Фонди. Но итальянский поход был всего лишь отвлекающим маневром, поскольку главной целью Барбароссы был Тунис.
16 августа 1534 года флот Барбароссы вошел в гавань Туниса. Под предлогом восстановления власти претендента на тунисский престол капудан-паша высадил своих янычар в Ла-Голетте, в самом узком месте канала, который вел к озерной гавани Туниса. Местный правитель Мулай Хасан бежал, и после легкой перестрелки Тунис сдался туркам. Страна была провозглашена владением Османской империи.
Эта новость очень не понравилась императору, который имел на Тунис свои виды. Карл V приказал собрать все боевые суда Испании, Неаполя, Сицилии и Мальты. Всего набралось до 600 кораблей под командованием Андреа Дориа (по другим данным, судов у генуэзского адмирала было лишь 400). Противостоять столь превосходящим силам купудан-паша не мог. Через месяц Тунис был захвачен союзным флотом, но Барбароссе удалось уйти с частью своих кораблей.
Союзный флот подошел к Тунису в конце июня 1535 года. На борту находились отряды императорских войск, состоявшие из испанцев, немцев и итальянцев. Вскоре они высадились вблизи руин Карфагена. Прежде чем достичь собственно Туниса, они должны были захватить башни-близнецы крепости Ла-Голетты, которые охраняли «горловину потока», ведущую к городу. Войска императора осаждали крепость в течение целых двадцати четырех дней, неся большие потери. Они долго не могли преодолеть отчаянное сопротивление турок. Крепость умело обороняли под руководством способного командира, корсара из Смирны (Измир), иудея по происхождению, с помощью артиллерии, взятой с находившихся в озерной гавани кораблей.
Но Ла-Голетта все-таки пала, в основном из-за проломов в стенах, появившихся в результате обстрела из орудий корабля рыцарей святого Иоанна – восьмипалубного галеона «Санта-Анна» огромных размеров, который, пожалуй, был самым вооруженным боевым кораблем из всех существовавших в то время.
Путь к Тунису для императорских войск был открыт. Овладев озером, они пленили основную часть флота Барбароссы. Однако капудан-паша, страхуясь от весьма вероятного поражения, направил эскадру своих галер в Бон, порт между Тунисом и Алжиром, спасая их таким образом от гибели. Он готовился встретить сухопутную армию императора, которая продвигалась по берегу озера в страшную жару. Потерпев неудачу в попытке блокировать ее продвижение к колодцам по маршруту следования, Барбаросса отошел под стены Туниса, где готовился дать сражение на следующий день во главе своей армии, состоявшей из турок и берберов.
Однако в Тунисе несколько тысяч пленных христиан под предводительством одного из мальтийских рыцарей вырвались на свободу, захватили арсенал и, вооружившись, атаковали турок. Император вошел в город, встретив лишь незначительное сопротивление. Но его солдаты устроили убийства, грабежи и насилия, продолжавшиеся три дня. На троне был восстановлен свергнутый Барбароссой прежний правитель Мулай Хасан, теперь уже в качестве вассала императора. Для охраны Ла-Голетты был оставлен испанский гарнизон.
Тем временем Барбаросса отплыл из Бона с галерами и войсками. Однако он пошел не в Стамбул, а атаковал испанские Балеарские острова. Испанцы такого поворота событий никак не ожидали. Турецкая эскадра под испанскими и итальянскими флагами была встречена с почестями, так как ее приняли за часть армады императора, возвращавшейся с победой. Корабли вошли в порт Маго (ныне Махон) на острове Минорка. Внезапно корабли открыли огонь и высадили десант. Город был сожжен, и войска Барбароссы, не встречая сопротивления, разграбили город, взяли в плен и в рабство 5700 христиан и увезли с собой в Алжир захваченные богатства и запасы.
В конце осени 1535 года Барбаросса с остатками флота вернулся в Стамбул. Султан приказал ему построить новый флот из 200 галер.
В 1536 году флот Андреа Дориа захватил у Мессины десять турецких торговых судов, а затем напал на турецкую эскадру у острова Панос в Ионическом море. В ответ весной 1537 года Барбаросса со своим новым флотом отплыл из Стамбула для нападения на юго-восточное побережье Италии. Оно должно было быть поддержано турецкой наземной армией под командованием султана, переброшенной морем из Албании.
Сулейман лично вел 20-тысячную армию через Фракию и вниз по Балканскому полуострову до порта Валлоны в Албании. А Барбаросса тем временем шел к Валлоне с флотилией из 100 кораблей. Там адмирал взял армию на борт, чтобы перевезти ее в Бриндизи. План также предполагал вторжение в Италию с севера войск французского короля Франциска I при поддержке турецких галер, присутствие которых на протяжении всей зимы в порту Марселя открыто демонстрировало франко-турецкий союз. В случае удачи Сулейман и Франциск надеялись изгнать Габсбургов из Италии. Турки подкупили губернатора Бриндизи, который обещал открыть ворота города. Но заговор был раскрыт и вариант с высадкой Бриндизи отпал. Тут еще выяснилось, что Франциск вступил с императором в переговоры о перемирии, раздумав вторгаться в Италию. Нужен был новый план военных действий. Сулейман и Барбаросса решили ограничиться разорением итальянского побережья. Адмирал высадил десанты в Отранто и, по свидетельству современников, «оставил пустынным побережье Апулии, подобно бубонной чуме».
Капудан-паша так напугал Андреа Дориа мощью своей армады, что тот не рискнул вывести свои корабли из порта Мессины.
Тем временем венецианские корабли захватили у Корфу турецкое судно, на котором находился губернатор Галлиполи, и убили весь экипаж и пассажиров. Лишь один моряк, держась за доску, доплыл до берега и сообщил о случившемся великому визирю. Сулейман приказал немедленно осадить Корфу. Его армия высадилась на острове с кораблей по понтонному мосту, составленному из лодок от албанского берега.