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