Отдав приказ авангарду двигаться вперёд, Велизарий ускоренным маршем шёл к своей цели, навстречу ему надвигались колонны вандальской конницы. Возле города Децима враги столкнулись. 13 сентября 533 г. передовые части вандалов опрокинули авангард римлян, и те поспешно отступили. Но на беду варваров их войска были разделены на три армии, и несогласованные действия полководцев погубили вандалов. Кроме того, брат Гелимера Аммат погиб в одной из схваток, что стало полной неожиданностью и страшным горем для короля. Пока он скорбел о покойном, римляне развернули свои силы и начали атаку — вандалы побежали. Только надвигающаяся ночь спасла их от полного истребления.
Желая закрепить успех, Велизарий не стал терять времени и двинулся вперёд к Карфагену, отдав строжайший приказ своим войскам не мародёрствовать — он крайне нуждался в поддержке местного населения[171]. 15 сентября 533 г. римляне вошли в полном порядке в Карфаген. Но это ещё не означало, что война закончена. Гелимер с остатками армии сосредоточился в Булла Регии и ожидал подхода войск с Сардинии под руководством своего другого брата Цацона, который разгромил восставших сардинцев во главе с Годом. Однако и у Велизария появились неожиданные союзники — вожди арабских племён, традиционно быстро менявшие объекты своих симпатий, быстро сообразили, в чьих руках удача и отправили к римлянам посольство с предложением мира[172].
Гелимер и Цацон встретились и, объединив свои силы, подошли к Карфагену на расстояние 30 км. Передовые отряды варваров испортили водопровод и практически отрезали Велизарию выходы из города. Но и римский полководец не сидел сложа руки: он спешно восстановил стены Карфагена. Объективно оценив своего врага как внешне грозного, но в действительности уступающего ему по силе, византиец не собирался отсиживаться в осаде и в середине декабря 533 г. вышел навстречу вандалам. Возле города Трикамара состоялась битва, где войска Велизария вновь одержали победу. Уже в начале сражения погиб Цацон, а упавший духом Вандальский король бежал, чем ввёрг в панику своих воинов. Атака тяжелой римской кавалерии — личной дружины Велизария, вновь сыграла решающую роль[173].
Удача следовала одна за другой: в погоне за Гелимером Велизарий встретил группу вандалов, передавших ему всю казну королевства, чем лишили своего правителя финансовых средств для пополнения армии. Сам Гелимер спрятался в крепости на горе Папуа, но Велизарий просто обложил её своими отрядами, а затем продолжил освобождение Африки. Посланный им на Сардинию отряд освободил остров от вандалов, и тот вошёл в состав Римской империи. Затем были освобождены Корсика и Балеарские острова. Весной следующего года сдался, наконец, и Гелимер, не выдержавший мук голода. Его привезли в Карфаген, и Велизарий с огромной добычей, варварским королём и 5 тыс. пленных вандалов отплыл в Константинополь.
Нельзя сказать, что этот неожиданный отъезд совпадал с планами Велизария. Но верные друзья из столицы сообщили ему, что кто-то посеял у императора сомнения в верности полководца, насплетничав, будто тот собирается образовать своё царство в Африке и стать его государем. Конечно, слух был беспочвенным, но сколько св. Юстиниан видел вокруг себя предательства, чтобы сходу отвергнуть такое серьёзное обвинение? От греха подальше, он предложил Велизарию вернуться обратно, и тот не стал множить сомнений императора. Осенью 534 г., по возвращении в столицу, ему был организован великолепный триумф в Константинополе, и в знак благодарности он получил консульство на 535 г.
По словам историка, 600 лет (!) Римская империя не видела такого триумфа[174]. Дочери и родственники покойного Гильдериха были приняты с надлежащим почётом как члены дома св. Феодосия Младшего и родственники императора. Пленные вандалы составили 5 новых полков и были отправлены на границу Сирии и Персии. Замечательно, что Гелимера не казнили, и ему даже предлагали титул патриция, если он откажется от арианства. Поскольку этого не произошло, бывшего Вандальского короля просто поселили как частного человека на вилле в Вифинии, где он и жил до конца своих дней, умерев естественной смертью[175].