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