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