Воодушевленный этими соображениями, Юстиниан собрал армию для вторжения в Африку летом 533 года, хотя многие его советники и в первую очередь финансист Иоанн из Каппадокии предостерегали его против нападения «на край земли, откуда любая весточка достигнет Византии не раньше чем через год». Странная просьба для любого, кто знаком с организацией древней империи. Армия была не слишком велика: в ней насчитывалось 10 000 пеших солдат и 5000 кавалеристов – наполовину регулярные войска из азиатских провинций, наполовину вспомогательные отряды гуннов и герулов. Но их командир – Велизарий – был исключительно надежным человеком, и уверенность в нем укрепляла дух людей. Морское путешествие из-за встречных ветров растянулось на восемьдесят дней, но, наконец, в начале сентября флот пристал в районе Капут-Вада, мыса, который «смотрит» на Сицилию. Вандалы были застигнуты врасплох. Их король находился в Нумидии, войска – на Сардинии, флот даже не был спущен на воду. Слепая вера в свою удаленность от Константинополя заставила вандалов проигнорировать все угрозы Юстиниана, и они даже не думали о возможности вторжения. Гейламир поспешил на берег, казнил пленного Хильдерика и стал собирать воинов отовсюду, откуда только было возможно. Но прошло еще одиннадцать дней, прежде чем он сумел собрать силы, достаточные для нападения на римлян, а Велизарий со своими людьми все это время двигался, не встречая сопротивления, к воротам Карфагена. Жители провинции встречали его с радостью. Ведь он объявил, что явился освободить их от арианского гнета. Его солдаты вели себя выше всяких похвал. Ни один дом не был разграблен.
Велизарий добрался до почтовой станции при Дециме и дальше продвигался со всеми возможными мерами предосторожности, постоянно ведя разведку. Внезапно на римлян напали крупные силы вандалов, которые превосходили их в численности в соотношении как минимум два к одному. Атака велась сразу с трех сторон. Один корпус вандалов под командованием брата короля Аммата атаковал с фронта (из Карфагена), другой – с левого фланга, а главные силы под командованием самого Гейламира – с тыла. Но вандалы были плохими тактиками и не сумели скоординировать атаки. Сначала появились войска из Карфагена и были отбиты, потеряв своего лидера, затем настала очередь войск с фланга, против которых Велизарий использовал гуннскую кавалерию. Когда подоспели главные силы вандалов, в центре и арьергарде походной колонны уже шли серьезные бои. Гейламир бросился в бой и с ходу рассек колонну противника надвое, однако понятия не имел, как использовать свое преимущество. Вместо того чтобы развить первый успех, он остановил своих воинов, позволив Велизарию собрать и переформировать своих людей. Говорят, он был так потрясен гибелью брата, труп которого обнаружил на поле боя, что больше не отдавал никаких приказов – только лежал на земле и рыдал. А римляне уже снова были в боевом строю.
Их победоносный авангард вернулся, чтобы помочь центру, и вечером римляне атаковали неподвижные массы вандалов. Завоеватели Африки, вероятно, утратили свою древнюю отвагу, поскольку, оказав ничтожное сопротивление, они под покровом ночи бежали на запад.
Карфаген сразу гостеприимно распахнул ворота, и уже на следующий день Велизарий обедал в королевском дворце, вкушая яства, приготовленные для короля вандалов. Гейламиру пришлось пожинать плоды сотни лет угнетения и гонений, которым его предки подвергали африканцев. Все города, где не было гарнизонов, распахивали ворота перед римлянами, а жители провинции отдавали все, что имели, в распоряжение Велизария. Его вход в Карфаген был как триумф вернувшегося домой короля, а порядок и дисциплина в войсках настолько высоки, что даже вандалы и ариане не понесли никакого ущерба.
Тем временем Гейламир удалился в горы Нумидии с армией, которая пострадала больше морально, чем физически. Там к нему присоединились войска, которые он послал на Сардинию. Покорив остров, они вернулись, и теперь численность армии Гейламира составила 50 000 человек. Обнаружив, что люди Велизария восстанавливают стены Карфагена, прежде чем двинуться дальше, вандал решил напасть первым. Спустившись с гор, вандалы двинулись на Карфаген и встретились с римской армией в районе Трикамерона, в двадцати милях к западу от города.
Здесь Велизарий выиграл генеральное сражение после схватки более ожесточенной и кровопролитной, чем при Дециме. Трижды римляне были вынуждены начать отступление, но их храбрый командир снова собирал их и вел вперед. Наконец, его кирасиры прорвались через ряды вандалов и убили Цазона, брата Гейламира. Король спасся бегством, а его люди продолжали сражаться, пока им не был отрезан путь к отступлению. Почти весь народ вандалов погиб в этом бою и последующем преследовании. Гейламир скрылся в Атласских горах среди мавров и несколько месяцев жил с ними, терпя лишения.