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