Карл снарядил армию около 30 тысяч человек. Во главе ее в качестве своего заместителя он поставил генерала дель Васто; герцогу Альбе как полковнику было подчинено восемь тысяч солдат. Альба взял с собой своего брата Бернардино, а также пятилетнего сынишку. Однако жестокосердие герцога, который перед лицом предстоящих лишений не пожалел малыша, вызвало нарекание.
Сопровождаемый благословением папы и совершенно противоположными мыслями французского короля, который втайне вступил в сношения с турками, император отплыл в конце мая из Барселоны и в середине июня 1535 года достиг африканского побережья, где солдаты и высадились.
Ключевым пунктом для нападения на Тунис была крепость Ла-Гулетта, которая находилась в нескольких милях от того места, где прежде был Карфаген. Среди офицеров императора Альба выделялся особо. Теперь 28-летний герцог не упускал ни одной возможности продемонстрировать Карлу свои способности. Исход сражения завис на острие ножа, однако, в конце концов, крепость была завоевана, а 21 июля 1535 года захвачен и город Тунис. Карл торжественно въехал в город. Герцогу Альбе за его заслуги было вручено оружие его погибшего отца, которое обнаружили в крепости.
До времени тунисского похода подъем Альбы, в соответствии с идеями императора о роли его испанских грандов, проходил медленно. Однако теперь ускорился. С Карлом Альба возвратился в Италию и 22 августа высадился в Сицилии Там его постиг жестокий удар: его брат Бернардино умер от лихорадки
Карл сполна насладился своей победой. Куда бы он ни прибыл, в его честь устраивали праздники, триумфальные въезды, служили благодарственные мессы. В сообщениях об этом почти везде можно встретить и имя Альбы. Однако перед ним всегда стоит кто-нибудь другой — то Андреа Дориа, то герцог Беневентский, маркиз дель Васто, Фердинанд Гонзага, герцог Брауншвейгский. Однако его уже не обходят молчанием Он становится знаменитостью, глаза зрителей ищут его в свите императора, на него указывают друг другу.
Очевидно, если исключить смерть Бернардино Толедского, то период с сентября 1535 года по март 1536 года был счастливым временем и для императора и для герцога. В октябре они перебрались из Сицилии через Термини, Козенцу, Салерно в Неаполь, где Карл провел зиму. Его пребывание там скрасили великолепные празднества. К Пасхе он прибыл в Рим. И вновь началась тяжелая работа. Новым папой стал Павел III, который собирался изменить папскую политику последних лет, освободить ее от влияния императора и его планов церковной реформы и сблизиться в политическом отношении с французским королем. На второй день Пасхи Карл рассказал ему о своем горьком опыте отношений с Францией. Однако он предвидел, что ему вряд ли удастся склонить папу на свою сторону, и был полон решимости и без папской поддержки вновь попытать счастья, выступив с оружием в руках против Франции. Большинство генералов пытались его отговорить. Они были готовы занять и разграбить Пьемонт и Савойю, но вступление войск во Францию казалось им слишком опасным. Тем не менее его желание поддержали трое полководцев: самый усердный, старый де Лейва, Андреа Дориа и герцог Альба. Первым двоим принадлежит роковая идея осадить Марсель. Один Альба высказал по-настоящему конструктивную мысль: оставить Марсель в стороне, захватить богатый Прованс и продвигаться в направлении Лиона. В этом мнении его укрепила рекогносцировка в направлении Марселя, которую он осуществил, проезжая с императором из Рима через Сиену, Флоренцию, Лукку и Асти, вплоть до французской границы. Однако он не смог настоять на своем. Совет де Лейвы значил в то время больше, чем совет Альбы. Марсель был осажден, и Альба пережил первое в своей жизни крупное поражение испанского оружия. Сам он не принимал в этом участия, поскольку перед ним были поставлены задачи в Провансе, с которыми он справился. Поскольку действовали вопреки его совету, ему было нетрудно настоять на отступлении, тем более что де Лейва вовремя умер.
Несчастье других гораздо чаще, чем собственное счастье, становится залогом нашего успеха. Крах похода на Марсель, смерть де Лейвы и другие неудачи побудили Карла назначить герцога Альбу своим главным военным советником. Наконец-то герцог, несмотря на зависть окружающих, достиг того, к чему стремился. Наряду с министром Николасом Перрено де Гранвеллой и секретарем Лос-Кобосом Альба занял при дворе самое влиятельное место, которое только мог дать Карл. Он вправе был гордиться своими успехами, когда в декабре 1536 года вместе с Карлом возвратился в Испанию.