Нельзя сказать, что всё происходило гладко: в дороге хлеб зацвёл, и почти 500 солдат отравились и умерли. Тогда Велизарий закупил зерно за собственные деньги и организовал свежую выпечку. Затем закончились запасы воды, и войска стали страдать от жажды. Наконец, византийцы достигли Сицилии, где Велизарий с удивлением узнал, что вандальский флот находится около Сардинии и враги вообще не в курсе его экспедиции. Такую неслыханную удачу нельзя было упускать из рук. Велизарий тотчас отдал приказ пересечь безопасное море и высадился в Триполитании, где их уже ждали восставшие против вандалов местные жители. 2 сентября 533 г. византийское войско спокойно высадилось в Капут Ваде, а через два дня они уже были в 19 км от Карфагена. Велизарий отправил гонца с посланием к Вандальскому королю, в котором объяснял, что война началась из-за нарушения установленного Гейнзерихом порядка престолонаследия. В ответ Гелимер отдал приказ казнить находившегося в темнице Гильдериха и его близких товарищей, что и было исполнено братом нового короля Амматом[170].

Отдав приказ авангарду двигаться вперёд, Велизарий ускоренным маршем шёл к своей цели, навстречу ему надвигались колонны вандальской конницы. Возле города Децима враги столкнулись. 13 сентября 533 г. передовые части вандалов опрокинули авангард римлян, и те поспешно отступили. Но на беду варваров их войска были разделены на три армии, и несогласованные действия полководцев погубили вандалов. Кроме того, брат Гелимера Аммат погиб в одной из схваток, что стало полной неожиданностью и страшным горем для короля. Пока он скорбел о покойном, римляне развернули свои силы и начали атаку — вандалы побежали. Только надвигающаяся ночь спасла их от полного истребления.

Желая закрепить успех, Велизарий не стал терять времени и двинулся вперёд к Карфагену, отдав строжайший приказ своим войскам не мародёрствовать — он крайне нуждался в поддержке местного населения[171]. 15 сентября 533 г. римляне вошли в полном порядке в Карфаген. Но это ещё не означало, что война закончена. Гелимер с остатками армии сосредоточился в Булла Регии и ожидал подхода войск с Сардинии под руководством своего другого брата Цацона, который разгромил восставших сардинцев во главе с Годом. Однако и у Велизария появились неожиданные союзники — вожди арабских племён, традиционно быстро менявшие объекты своих симпатий, быстро сообразили, в чьих руках удача и отправили к римлянам посольство с предложением мира[172].

Гелимер и Цацон встретились и, объединив свои силы, подошли к Карфагену на расстояние 30 км. Передовые отряды варваров испортили водопровод и практически отрезали Велизарию выходы из города. Но и римский полководец не сидел сложа руки: он спешно восстановил стены Карфагена. Объективно оценив своего врага как внешне грозного, но в действительности уступающего ему по силе, византиец не собирался отсиживаться в осаде и в середине декабря 533 г. вышел навстречу вандалам. Возле города Трикамара состоялась битва, где войска Велизария вновь одержали победу. Уже в начале сражения погиб Цацон, а упавший духом Вандальский король бежал, чем ввёрг в панику своих воинов. Атака тяжелой римской кавалерии — личной дружины Велизария, вновь сыграла решающую роль[173].

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

Нельзя сказать, что этот неожиданный отъезд совпадал с планами Велизария. Но верные друзья из столицы сообщили ему, что кто-то посеял у императора сомнения в верности полководца, насплетничав, будто тот собирается образовать своё царство в Африке и стать его государем. Конечно, слух был беспочвенным, но сколько св. Юстиниан видел вокруг себя предательства, чтобы сходу отвергнуть такое серьёзное обвинение? От греха подальше, он предложил Велизарию вернуться обратно, и тот не стал множить сомнений императора. Осенью 534 г., по возвращении в столицу, ему был организован великолепный триумф в Константинополе, и в знак благодарности он получил консульство на 535 г.

По словам историка, 600 лет (!) Римская империя не видела такого триумфа[174]. Дочери и родственники покойного Гильдериха были приняты с надлежащим почётом как члены дома св. Феодосия Младшего и родственники императора. Пленные вандалы составили 5 новых полков и были отправлены на границу Сирии и Персии. Замечательно, что Гелимера не казнили, и ему даже предлагали титул патриция, если он откажется от арианства. Поскольку этого не произошло, бывшего Вандальского короля просто поселили как частного человека на вилле в Вифинии, где он и жил до конца своих дней, умерев естественной смертью[175].

Сразу после окончания этой победоносной кампании, повергшей всех — и врагов, и царский двор — в изумление, император принялся восстанавливать управление Северной Африкой. Как и в старые времена, были обозначены семь провинций, руководимых префектами претория со штатом чиновников. Назначили и пятерых военачальников, в чьи обязанности входило обеспечение безопасности этих земель. Первоначально св. Юстиниан довольно снисходительно отнёсся к арианскому духовенству, донатистам и иудеям, чем вызвал серьёзное недовольство со стороны Карфагенской церкви и даже Римского папы. Несколько преувеличивая свои возможности в Африке, император не считался с тем, что годы вандальской оккупации изменили жизнь в этих провинциях, а также не учитывал агрессивности диких племён, граничащих с римскими провинциями. Он отдавал распоряжения с таким размахом, будто речь шла об обычной римской провинции, находившейся глубоко в тылу. К сожалению, эта искусственная политика через некоторое время принесла свои дурные плоды[176].

Едва Велизарий удалился в столицу, как тут же арабские племена начали привычный для них обычный грабёж цивилизованных территорий, не особенно интересуясь, под чьей властью те находятся. Один за другим гибли римские военачальники, пытавшиеся во главе своих слабых отрядов отбить нападения кочевников, только один из них — Соломон, товарищ Велизария по оружию, сумел разбить арабов в затяжном походе вглубь их территории. Но его успехи были крайне ненадёжны: многие оставшиеся римские солдаты, ариане по вероисповеданию, переженились на пленных вандалках, и в армии началось брожение, подогреваемое арианскими священниками. Часть помилованных св. Юстинианом вандалов вернулась на родину и восстала[177]. Весной 536 г. ситуация стала особенно тревожной: мятежники решили убить Соломона и захватить Карфаген. Первая часть их плана не удалась, но зато город был подвергнут грабежу, после чего они почему-то решили оставить город и организовать свою стоянку в Булла-Регии; командование над собой они предоставили некоему Стотца.

Этот бунтарь по крови, но талантливый военачальник и организатор, быстро понял ошибку своих товарищей и первым делом решил занять Карфаген. По счастью, в Сицилии в это время находился Велизарий со своим войском. По приказу императора он должен был начать военные действия в Италии, но, получив известия из Африки, немедленно повернул на Карфаген и вошёл в город буквально накануне того дня, когда им собирался овладеть Стотца. При нём было всего 100 человек его личной дружины, но слава полководца была такова, что уже на следующий день он имел под рукой 2 тыс. воинов, а в лагере Стотца началось повальное бегство. Близ города Мембресы противники встретились, и византийский полководец в очередной раз показал свои лучшие качества: мятежники были разбиты наголову, а Стотца бежал в Нумидию[178].