Один из его командиров, гот Года, захватил Сардинию, провозгласив себя королём. Для его смещения Гелимер отправил на Сардинию 5 тыс. воинов под началом своего брата Цазона. На востоке королевства вандалов жители Триполиса перешли под власть Византии, для их подчинения у вандалов уже не хватало сил.
Спустя 3 месяца после начала похода византийская армия высадилась на африканском берегу в 5 днях пути (для пешехода налегке) к востоку от Карфагена. Оттуда солдаты двинулись в сторону Карфагена вдоль побережья, византийский флот сопровождал их. Когда войско подошло к городку Децим в 13 км от Карфагена, произошло первое сражение с вандалами.
План Гелимера заключался в одновременной атаке Велизария с 3 сторон. Сам Гелимер с конницей нападает с тыла, его брат Аммата – с фронта (из Карфагена), его племянник Гибамунд с 2 тыс. воинов атакует с юга, прижимая византийцев к морю.
В середине сентября 533 года войско Гелимера было разбито по частям в сражении при Дециме. Аммата и Гибамунд погибли, сам он бежал в глубинные районы Нумидии. Велизарий занял без боя Карфаген, оставшийся без войск. Пока Велизарий укреплял Карфаген как свой опорный город в стране вандалов, Гелимер развязал партизанскую войну, выплачивая вознаграждение за вражескую голову. Его попытка призвать на помощь везеготов из Испании провалилась, вожди берберских племён решили выжидать, сохраняя нейтралитет, подкреплённый деньгами и подарками Велизария. Некоторая часть мавров всё же присоединилась к Гелимеру. На помощь к вандальскому королю вернулся его брат Цазон из Сардинии.
Следующее сражение произошло в середине декабря 533 года у Трикамара в 25 км от Карфагена. Византийцы отбросили вандалов в их укреплённый лагерь, после чего отошли назад. Были убиты Цазон и ещё 800 вандалов, потери византийцев составили около 50 человек. Неожиданно для всех Гелимер тайно бежал. Узнав об этом, стали разбегаться оставшиеся вандалы с семьями. Лагерь с богатой добычей попал в руки византийцев без боя, после этого вандалы нигде не оказывали организованного сопротивления, но укрывались в храмах. Вся северная Африка от Гибралтара до Триполиса перешла под контроль Византии.
Как заметил Прокопий, война была выиграна 5 тысячами всадников, пехота практически не успела принять участия в боях. Общее число воинов у вандалов осталось неизвестным. Прокопий упомянул, что когда Гелимер послал 5 тыс. воинов в Сардинию, то это были все боеспособные силы вандалов. В распоряжении Гелимера в Африке оставалось сравнимое число воинов, если судить по описанию хода сражения при Дециме. Гелимер укрылся на горе Папуа под защитой преданных ему мавров. Всю зиму его осаждал там отряд герулов. Через 3 месяца лишений в начале весны 534 года последний король вандалов и аланов сдался, после чего был отправлен в Константинополь. 2 тыс. пленных вандалов в составе византийских войск были посланы на войну с персами. Королевство вандалов и аланов прекратило своё существование.