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