Поход начался весной 533 года под командованием Белизария, после того как за его успешное завершение молился патриарх на пристани Золотого Рога, и теперь оставалось лишь ждать, сумеет ли Юстиниан поддержать своего командующего и армию в этом внушительном, предпринятом им проекте. Армия, вверенная Белизарию, была всё же слишком мала, чтобы противостоять воинственным силам вандалов и готов. Сам Юстиниан боялся, что Белизарий решит остаться в Африке в качестве полноправного монарха, если поход увенчается успехом.

Великий Теодорих начал восхождение к власти с должности командующего войсками в империи. Африканское побережье богато и плодородно. Если солдаты доберутся туда, то станут подчиняться Белизарию, а не Юстиниану. Десятитысячная армия была против этого похода, потому что большинство солдат хотели вернуться на родину после войны с персами, четыре сотни гуннов не желали плыть морем, так что основная сила заключалась в нескольких тысячах «закованных в железо» из полка Белизария. Более того, молодой талантливый полководец взял с собой свою семью, супругу, актрису Антонину и взрослого крестного сына Феодосия. Это привело к беде, но не той, что ожидал Юстиниан.

Первая задача командующего — установить подобающий авторитет среди своих солдат. Пятьсот маленьких кораблей флотилии, необходимые для переправы армейских запасов и пяти тысяч лошадей, принадлежали в основном сирийским и египетским купцам и никогда ещё не пускались в дальние морские плавания. Белизарий повелел выкрасить в красный цвет паруса трёх флагманских кораблей и привязать на шестах над мачтами фонари, чтобы можно было плыть ночью и чтобы вся флотилия следовала в один ряд. Иначе будущие корабли просто бы наталкивались друг на друга, с наступлением темноты заходя в маленькую гавань. Прокопий пишет, что гребцы мастерски управлялись со своими судёнышками, искусно работая вёслами. Запасы воды портились в непригодных ёмкостях. Антонина, жена командующего, сохраняла свой запас питьевой воды чистым и прохладным в стеклянных кувшинах, спрятанных в мешки с песком. «Эта женщина, — замечает Прокопий, — умела найти выход даже из самой безвыходной ситуации». Галеты, выданные экономистом, — Иоанн из Каппадокии был снова на посту, потому что он один мог собрать нужную сумму для ведения войны и перестройки Константинополя, — заплесневели, вследствие чего многие погибли от дизентерии. Белизарий высадился на берег и на свои деньги закупил зерна, а также посадил на кол двух гуннов, которые напились и убили своего товарища. Это был серьёзный шаг. Гунны, бесценные в битве, не признавали римских законов и военной дисциплины. После казни Белизарий не мог быть полностью уверен, что они не восстанут против него.

Итак, эта злосчастная флотилия приставала к берегу у каждого острова. Армейские командиры, завидуя молодому Белизарию и готовые выступить против него, заявили, что их солдаты на таких кораблях не желают вступать в битву с вандалами на море.

Солдаты не знали, что ждёт их там, на берегу, где в течение трёх столетий проживали вандалы, они лишь видели, что жалкие остатки последнего императорского флота бросают вызов вандалам — завоевателям Африки.

Они высадились на Сицилии, у подножия горы Этна. Территория принадлежала готам. Белизарий волновался, потому что за время долгого пути корабли поистрепались, а люди ослабели. Прокопий вспоминает: «Ступив на берег, он не находил себе места, не знал, куда дальше идти, и терзался сомнениями, потому что не представлял, какие воины вандалы или как объявить им войну, а его солдаты были объяты страхом, говоря, что не могут сражаться сразу с двумя противниками — вандалами и морем».

Сириец Прокопий начал восхищаться Белизарием и, к счастью, смог разрешить сомнения полководца. Отправившись в Сиракузы за информацией, он встретил слугу, приехавшего три дня назад из Карфагена — столицы и морского порта вандалов, места, где обычно находились король, армия и флот. Однако Юстиниану удалось расчистить путь для своих воинов. Его шпионы распространили слух о движении императорских сил по пустынному побережью недалеко от Триполи и на далёком острове Сардиния. В результате флот вандалов и пятитысячная армия были переброшены на Сардинию, а король Гелимер со своим двором четыре дня назад покинул Карфаген, не подозревая, что на море уже находятся войска Белизария.

Более того, благодаря переписке Юстиниана с готским двором его флоту удалось заправиться на Сицилии. Как можно скорее Белизарий вышел в море, направляясь к Мальте, откуда благоприятный восточный ветер доставил бы его в Африку.

Флот причалил в месте, известном римлянам под названием Отмель, но до желанного Карфагена было ещё далеко. Пустынный красный берег выглядел недружелюбным. Командующий, стремящийся быстро продвигаться вперёд, созвал военачальников на корабль и спросил их мнения. Военный совет проголосовал за то, чтобы взойти на корабли и, обогнув мыс, плыть к Карфагену. Это заняло бы девять дней без запасов воды, а на этом бесприютном берегу армию мог бы легко застигнуть шторм.

Вероятно, командиры хотели расчистить путь для отступления. Белизарий мог быть одновременно вежливым и очень едким. «Я не виню вас, — ответил он, — в этой пустыне нельзя найти приюта. Но я согласен с вами в одном: нельзя одновременно встречаться с вандалами и морем. Всё, что вы говорите, — правда, если разразится шторм, с нашими кораблями случится одно из двух: либо их отнесёт далеко от берега, либо они утонут. А если мы будем на кораблях, то что может случиться с нами?» Он посоветовал быстро передвигаться по суше, чтобы добраться до Карфагена прежде, чем враг опомнится и начнёт защищать город. После этого корабли вдоль побережья дойдут до гавани, и Карфаген со всем своим богатством и запасами будет служить базой для дальнейших действий. Таким образом армия сможет найти убежище в стенах города. Все согласились. Прокопий с радостью заявил, что вода, которую они нашли в подземном источнике на первом привале, — хорошее предзнаменование. Но Белизарий, его солдаты и конные гунны были не в настроении задерживаться дольше. Полководец поторопил армию и жестоко наказывал тех, кто осмеливался забирать во встречающихся деревнях фрукты и живность. «Эти деревенские жители — римляне, они будут помогать нам, если мы не вынудим их помогать вандалам. Почему вы так настойчиво наживаете себе врагов?»

Белизарий принудил своих солдат расплатиться серебром за продовольствие и тронулся в дальнейший путь. Он шёл почти по тому же самому маршруту, что и восьмая армия африканского корпуса Роммеля спустя более чем четырнадцать веков, когда Карфаген уже стал Тунисом.

Войскам не удалось быстро подобраться к Карфагену. Когда римляне увидели естественные защитные сооружения огромного порта, цепь холмов, оканчивающуюся сухим солёным озером и великим озером Карфагена, то их доброжелатели, крестьяне, которым заплатили серебром, сообщили, что вандальские всадники прибывают в город со всех сторон. Белизарий остановил свою колонну и выстроил лагерь, окружённый по старинке выкопанными рвами. Там остался его багаж, более слабые соединения пехоты и его жена Антонина. Сам он, оставив свой полк в тылу, так как это были единственные силы, на которые он мог рассчитывать, пошёл по главной дороге, которая вилась меж холмов и озёр к Карфагену.