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