После смерти АРУДЖА БАРБАРОССЫ в 1518 году Хайреддин начал вести яростную борьбу за то, чтобы отстоять территории, завоеванные его старшим братом. Он установил прекрасные отношения с султаном Селимом I (1512 — 1520). Однако владыка ОСМАНСКОЙ империи, занятый покорением Сирии и Египта, вряд ли мог оказать ему весомую военную помощь. В 1518 году сильнейший шторм практически уничтожил большую испанскую экспедицию, высланную для усмирения АЛЖИРА. Местная оппозиция вынудила Хайреддина спасаться бегством. В Джиджеле он и пробыл с 1520 по 1522 год. Находясь там, он значительно увеличил собственное богатство, совершая набеги на побережья Сицилии и Испании.
К 1525 году Рыжебородый вернул себе верховную власть в Алжире в качестве представителя султана Сулеймана I (1520 — 1566) и создал весьма внушительный корсарский флот. После того как в 1522 году Сулейман завоевал РОДОС, Хайреддин смог, наконец, получить турецких солдат и более мощную артиллерию. В 1529 году он осуществил свою давнюю мечту — взял штурмом испанскую крепость в гавани Алжира и разрушил ее до основания. Испанская армада устремилась было в контратаку, однако, встретившись с основным флотом Барбароссы, решила уклониться от боя.
Хайреддин ввел в Алжире систему государственного устройства, подобную той, которую Османская империя ввела незадолго до этого в Египте. Он удостоился титула БЕЙЛЕРБЕЯ (то есть вице-короля) Северной Африки, получил в свое распоряжение 2000 отборных янычар и право дополнительно просить в случае необходимости войска из Турции. Регулярная армия обеспечивала власть в основном вокруг города Алжира, а правление на местах было поручено вождям местных племен. Время от времени янычары совершали походы во внутренние земли с целью сбора налогов.
Хайреддин Барбаросса подавляет восстание жителей Алжира (примерно 1520 год). Иллюстрация Леопольда Флэменга из книги Чарлза Фэрайна "Два пирата”, 1869 год
В 1533 году султан Сулейман вызвал Хайреддина в Константинополь и назначил его начальником морских сил (капудан-пашой) Османской империи. В первую очередь такой выбор был продиктован успехами Барбароссы в Северной Африке. Теперь Сулейман позволял себе мечтать даже о завоевании Испании и освобождении мусульманской части ее населения.
Хайреддин вместе со своими капитанами-корсарами реорганизовал турецкий флот, который затем направился в ТУНИС, расположенный между Константинополем и основной базой корсаров в Алжире. В 1534 году призванные на государственную службу пираты и войска османов легко победили Мулай Хасана — весьма непопулярного тунисского султана. В июле следующего года испанский король Карл V лично возглавил поход на Тунис, собрав для этой цели 400 кораблей и 30 000 солдат. Несмотря на яростное сопротивление, испанцы вернули себе город, убили тысячи его защитников и вновь сделали Мулай Хасана правителем-марионеткой. В отместку за Тунис Хайреддин напал на Майорку и разграбил остров, взяв в плен 6000 человек и захватив огромное количество добычи.
Начиная с 1535 года адмирал руководил османским флотом из Константинополя. Летом 1537 года он вместе с Люфти-пашой, премьер-министром султана, возглавил огромную флотилию — из примерно 250 галер, дополненных многочисленными корсарскими кораблями — собранную для покорения Южной Италии. Османы прошлись огнем и мечом по территориям вокруг Отранто. Однако султан Сулейман решил не перевозить основные силы турецкой армии через проливы со стороны Албании.
На следующий год Хайреддин ввел турецкий флот в Эгейское море. Его лейтенантами были ТУРГУТ и САЛИХ РЕЙС. Османы подчинили себе острова, ранее принадлежавшие Венеции, и Геную, ограбили южное побережье Крита, а потом повернули на север и вышли в Ионическое море. В заливе ПРЕВЕЗА они встретились с объединенным флотом Венеции, Папы римского, Генуи и Испании. Присущее Барбароссе мастерское владение тактикой ведения боевых действий на море силами галер решило исход сражения в пользу турок. Этот триумф укрепил господство Османской империи в Ионическом море.
Для своей последней кампании Хай-редцин вернулся в западную часть Средиземноморья. В 1542 году и султан Сулейман I, и король Франции Франциск II находились в состоянии войны с Карлом V. Ввиду очевидной слабости флота Франции, последняя предложила субсидировать боевые операции турков на море. Для начала французы пригласили флот османов провести зиму 1543 — 544 годов в Тулоне (Южная Франция).