У него были основания верить в себя и пренебречь мнением советников. Византийская армия к тому времени сильно изменилась, и ее боевые порядки уже ничем не напоминали те неуклюжие колонны, которые были разгромлены готами в сражении при Адрианополе в 378 году. Теперь большую роль в ней играла конница, способная противостоять самому мобильному противнику. А поскольку экипировка и вооружение всадников были делом затратным, некоторые подразделения были фактически личными дружинами состоятельных офицеров, которые платили им из собственного кармана. Эти командиры были важны для Юстиниана, поскольку, в отличие от Константина, Валента и Феодосия I, он никогда не вел свои войска в бой лично и ему нужно было найти надежного военачальника для войны на западе. Выбор пал на Велизария, конница которого насчитывала больше тысячи воинов. Назначение это было несколько спорным. Именно Велизарий одержал блестящую военную победу над персами у крепости Дара в 530 году, но год спустя показал себя куда хуже в битве при Каллинике и, как некоторые говорили, покинул тогда поле боя, уплыв по реке Евфрат в лодке. Вполне вероятно, однако, что главной причиной этого выбора стало богатство Велизария, поскольку Юстиниан не желал вкладывать слишком много в эту кампанию: он предоставил Велизарию всего 15 000 человек, на порядок меньше той армии, которая потерпела поражение в 468-м. Поэтому собственные ресурсы командующего должны были сыграть решающую роль в успехе кампании.
Как оказалось, выбор был удачным, и мрачные прогнозы не подтвердились. Военная кампания Велизария была исключительно успешной. Высадившись в Капут-Ваде (современный Тунис) летом 533 года, византийская армия застала вандалов врасплох и двинулась на Карфаген, не встречая какого-либо сопротивления. Только когда она была уже в 15 километрах от города, Гелимер со своим войском подоспел, чтобы преградить ей дорогу. В последовавшем коротком сражении византийцы разгромили вандалов и уже через несколько дней торжественно вступили в Карфаген. В начале следующего года король Гелимер и вандалы сдались, и провинции Северной Африки вновь стали частью Византии. В конце лета Велизарий вернулся в Константинополь, чтобы принять участие в триумфальном шествии, после которого на ипподроме плененный Гелимер преклонил колени перед победителем Юстинианом. Впечатляющая победа в Африке был увековечена в мозаике, которая украсила внутренние своды новых Медных ворот Юстиниана.
Столь быстрый и полный разгром вандалов, очевидно, подвиг Юстиниана на мысли о новых завоеваниях, и подходящий повод вскоре представился. В 526 году в Равенне умер король остготов Теодорих Великий, победитель Одоакра. Он был похоронен в великолепном мавзолее, который заранее для себя построил. На престол взошел его восьмилетний внук Аталарих, а мать мальчика, Амаласунта, стала регентом и опекуном короля. К несчастью, Аталарих оказался сущим наказанием для своей многострадальной матери: повзрослев, он, что называется, попал в плохую компанию и часто впадал в продолжительные запои. Амаласунта стала тревожиться за свое политическое будущее, которое выглядело одинаково мрачным независимо от того, достигнет ли ее своенравный сын совершеннолетия или же упьется до смерти раньше. Поэтому она вступила в тайные переговоры с Юстинианом в надежде добиться от византийцев военной помощи в борьбе против своих врагов. События, однако, развивались слишком быстро. В октябре 534 года Аталарих умер, а ближайшим его родственником оказался немолодой уже кузен Теодахад, человек довольно образованный. Вероятно, его бы вполне устроило, если бы все пошло как раньше: он был бы королем – номинально, а реально страной правила бы Амаласунта. Но ему не удалось избежать правления. Сношения Амаласунты с Константинополем вызвали подозрения, и советники Теодахада, родственники которых были казнены по ее приказу, призвали его нанести удар, прежде чем она договорится с императором о вводе в Италию византийских войск. Весной 535 года Амаласунта была схвачена и отправлена в заключение со строгим режимом изоляции подальше от Равенны, на берега озера Больсена. А вскоре после этого она была убита при загадочных обстоятельствах.