Отважные рыжебородые сыновья гончара, христианского вероотступника, ушедшего в отставку из корпуса янычар и женатого на вдове греческого священника, они были турецкими подданными с острова Лесбос, известного центра христианского пиратства, господствовавшего над входом в Дарданеллы. Став одновременно корсарами и торговцами, они устроили свою штаб-квартиру на острове Джерба, что между Тунисом и Триполи, удобном трамплине, с которого можно было нападать на судоходные пути и совершать налеты на побережья христианских государств. Имея гарантии защиты со стороны правителя Туниса, Арудж подчинил себе многих местных вождей племен и наряду с другими портами освободил от испанцев Алжир. Однако, попытавшись утвердить свое присутствие в глубине материка, в Тлемсене, он потерпел поражение и погиб от рук испанцев, сражаясь, как сказано в хронике, «до последнего вздоха, подобно льву».

После его гибели в 1518 году Хайреддин Барбаросса, подтверждая, что он был наиболее способным из двоих братьев-корсаров, стал крупным флотоводцем на службе у турок в Средиземном море. Сначала он укрепил свои гарнизоны, расположенные вдоль побережья, и заключил союзы с арабскими племенами внутренних территорий. Затем он установил контакты с султаном Селимом, который завершил завоевание Сирии и Египта. Его правый фланг мог быть с выгодой для него прикрыт силами соотечественников-османов на побережье Северной Африки. Барбаросса, как гласит запись, направил в Стамбул корабль с богатыми подарками султану, сделавшему его бейлербеем Африки, выслав в Алжир традиционные атрибуты должности — лошадь, турецкую саблю и знамя с двумя бунчуками, — а также оружие, отряд солдат и разрешение облагать налогами других. Еще Барбаросса получил привилегии янычар.

Только в 1533 году преемник Селима Сулейман, до того времени занятый сухопутными кампаниями в Европе, вступил в контакт с Барбароссой, подвиги которого в столкновениях с силами императора в Западном Средиземноморье не остались без внимания. Но сейчас султана беспокоило проникновение годом раньше морских сил христиан из западной части Средиземноморья в восточную. Ими командовал опытный генуэзский адмирал Андреа Дориа, который сменил лояльность королю Франции на верность Габсбургу. Пройдя Мессинский пролив, Дориа вошел в турецкие территориальные воды для захвата Корона, что на северо-западной оконечности Греции. Он надеялся таким путем создать тактический отвлекающий маневр в то время, когда султан вел осаду Гюнса, что недалеко от Вены. Султан направил сухопутные войска и флот, которые, несмотря на численное превосходство, не смогли отбить Корон. Хотя позже христиане были вынуждены оставить порт, Сулейман был озадачен этой неудачей, осознав, что, пока он укреплял сухопутные силы, состояние его военно-морского флота ухудшилось до такого уровня, когда он перестал быть равным морским силам Запада. Требовались решительные и, главное, неотложные меры по реорганизации, поскольку султан был накануне начала кампании против Персии и нуждался в обеспечении защиты морских рубежей империи в его отсутствие.

И Сулейман направил посла в Алжир, приказав Барбароссе явиться к нему в Стамбул. Не проявляя спешки, как и приличествовало его статусу правителя, Барбаросса в надлежащее время провел в величественном церемониальном строю сорок ярко расцвеченных судов своего берберского флота через Дарданеллы, вокруг мыса Сераль в бухту Золотой Рог. Он привез царские подарки султану — золото, бриллианты, драгоценные ткани, бродячий зверинец львов и других африканских животных, также большую группу молодых христианских женщин для гарема султана, каждая из которых несла подарок из золота или серебра. Барбаросса, с побелевшей бородой, свирепыми кустистыми бровями, но все еще здоровый и сильный физически, засвидетельствовал почтение султану на аудиенции в диване, сопровождаемый капитанами восемнадцати галер, закаленными морскими волками, которым были пожалованы почетные одежды и денежные пособия. Сам Барбаросса был назначен капудан-пашой, или главным адмиралом. Получив задание султана «показать свое умение в строительстве кораблей», они направились на имперские верфи, чтобы осуществить надзор, ускорить и внести улучшения в ведущиеся работы по строительству. Благодаря их усилиям в ходе зимы морская мощь султана вскоре распространилась по водам всего Средиземного моря и на большую часть североафриканского побережья.

Барбаросса был убежденным сторонником активного сотрудничества Турции с Францией в Средиземноморье. Он видел в этом союзе эффективный противовес морской мощи Испании. Это отвечало и планам султана, который теперь намеревался продолжить борьбу против императора Карла скорее на море, чем на суше, и также планам короля Франциска, которому это обещало помощь на море против итальянских государств императора, причем напрямую здесь, в Средиземноморье, а не косвенно — в отдаленном бассейне Дуная. Такая политика привела к подписанию турецко-французского договора 1536 года, содержащего секретные статьи о взаимной обороне.

Тем временем летом 1534 года, незадолго до отъезда султана в Персию, Барбаросса направился со своим отремонтированным флотом через Дарданеллы в Средиземное море. Флоты этого времени, типичным представителем которых был флот Барбароссы, состояли главным образом из больших галер, «броненосцев» своего времени, приводимых в движение гребцами, в основном рабами, захваченными в плен в сражениях или каким-либо иным способом. Также в них входили компактные галеоны, «эсминцы» XVI века, меньшие по размерам и более быстроходные. Гребцами на них были по большей части свободные люди, имеющие профессиональные навыки. Еще в них были галеоны, «линейные корабли», приводимые в движение только парусами; и галеасы, приводимые в движение частично парусами и частично гребцами.

Барбаросса решил продвигаться в западном направлении, чтобы разорить побережья и порты Италии вдоль Мессинского пролива и к северу от него, во владениях Неаполитанского королевства. Но его главной целью был Тунис — королевство, ослабленное кровопролитными распрями в местной династии Хавсидов, которое он обещал султану. Барбаросса стал подумывать о создании османской территории под собственным эффективным управлением, которая простиралась бы вдоль всего побережья Северной Африки, от Гибралтарского пролива до Триполи, включив в себя цепь удобных портов и гаваней. Под предлогом восстановления власти беглого принца династии он высадил своих янычар в Ла-Голетте, в самом узком месте канала, который вел к озерной гавани Туниса. Здесь, будучи свободными пиратами, он и его брат Арудж в прошлом укрывали свои галеры. Барбаросса был готов начать атаку. Но его репутация и сила были ныне таковы, что правитель Туниса Мулей-Хасан бежал из города, претендент на его трон отрекся, и Тунис был аннексирован Османской империей. Это дало туркам стратегический плацдарм, господствовавший с южной стороны над узким проливом, соединявшим восточную и западную часть Средиземноморского бассейна, в пределах досягаемости для галеры до Мальты, где теперь базировались бывшие рыцари Родоса (рыцари святого Иоанна), и до Сицилии. Остров Сицилия был когда-то завоеван именно с этого плацдарма сначала Карфагеном, а позднее — сарацинами, и теперь он, определенно, стал ближайшей целью османов в Средиземноморье.

Император Карл сразу осознал опасность — вероятно, Сицилию будет невозможно удержать. Сначала он попытался противостоять ей с помощью интриги. Он направил генуэзского посла, хорошо знавшего Северную Африку, лазутчиком в Тунис, поручив ему поднять мятеж против турок при поддержке свергнутого правителя Мулей-Хасана. На случай, если мятеж не удастся, он должен был либо путем подкупа склонить Барбароссу к измене султану ради императора, либо организовать его убийство. Однако Барбаросса раскрыл заговор, и генуэзца-лазутчика приговорили к смерти.