Надо сказать, Господь действительно благоволил св. Юстиниану, хотя складывается небезосновательное впечатление, что преференции, так неожиданно дарованные ему в войне с вандалами, были в значительной степени плодами рук самого императора. Как только Гелимер начал готовиться к войне, внезапно выяснились неприятные для него детали. Первой неожиданностью стало восстание правителя провинции Триполитаны Пуденция, который решил отделиться от Вандальского царства. Он направил Римскому императору послание с признанием его власти и с просьбой о помощи. Туда немедленно был отправлен отряд под руководством полководца Таттимута, и вскоре Триполитана признала себя частью территории Римской империи. Одновременно с этим восстала Сардиния, где мятеж возглавил гот Года – трудно отделаться от ощущения, что эти события были подготовлены тайной византийской дипломатией. Гелимер направил в Сардинию войска, но Велизарий, которому поручено было возглавить эту чрезвычайно рискованную экспедицию, уже приближался к берегам Африки212.
21 июля 533 г. римская армия отплыла из Константинополя на 100 транспортных судах, причем войско, доверенное Велизарию, было довольно немногочисленным. В состав экспедиционного корпуса входило 16 тысяч воинов: фракийцев, готов, герулов, гуннов. Наиболее боеспособной частью армии была личная дружина Велизария, состоявшая из настоящих профессионалов, приобретших богатый опыт на войне с Персией. Флот направился к Гераклее, где на суда погрузили лошадей, необходимых для римской кавалерии – третьей части армии213.
Нельзя сказать, что все происходило гладко: в дороге хлеб зацвел, почти 500 солдат отравились им и умерли. Тогда Велизарий закупил зерно за собственные деньги и организовал свежую выпечку. Затем закончились запасы воды, и войска стали страдать от жажды. Наконец, византийцы достигли Сицилии, где Велизарий с удивлением узнал, что вандальский флот находится около Сардинии и враги вообще не в курсе его экспедиции. Такую неслыханную удачу нельзя было упускать из рук. Велизарий тотчас отдал приказ пересечь безопасное море и высадился в Триполитании, где их уже ждали восставшие против вандалов местные жители.
2 сентября 533 г. византийское войско спокойно высадилось в Капут Ваде, а через два дня они уже были в 19 км от Карфагена. Велизарий отправил гонца с посланием к Вандальскому королю, в котором объяснял, что война началась из-за нарушения установленного Гейнзерихом порядка престолонаследия.