Юстиниан отступил, но не отказался от своего плана. Даже сны и видения, и его собственные, и якобы привидевшиеся другим, усиливали его ненависть к иноверцам. В конце концов, он принял решение и выполнение его поручил Велизарию, заслужившему доверие императора кровавым подавлением опасных волнений в Константинополе.

Вместе с полководцем в Африку, в качестве его советника по гражданским вопросам, отправился давно уже связанный с ним Прокопий. Ему суждено было стать летописцем этой войны — только благодаря его трудам мы точно знаем, как проходили военные действия. Сопровождала Велизария и его жена Антонина.

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

На Сицилии удалось также купить лошадей, а самое главное — получить важное благоприятное известие. На Сардинии, которая тогда была под властью вандалов, взбунтовался гарнизон, состоявший из греческих наемников. Их командир обратился к императору за помощью, хотя в сущности он стремился избавиться от любой власти и получить независимость. В это же время признала над собой власть Юстиниана африканская Триполитания. И наконец, что могло показаться уж вовсе поразительным, сам Гелимер не предпринимал никаких приготовлений к отражению нападения! Возможно, он ничего не знал о том, что к берегам Африки отправилась эскадра? Но это маловероятно. Скорее всего, он пренебрег известиями о приближении военных кораблей Константинополя — счел, что ему нечего опасаться, и этот флот будет так же легко разбит, как и предыдущий. Гелимер вел себя так, как будто с этой стороны никакая опасность ему не угрожала: большую часть своего сильного флота он отправил на Сардинию, а сам покинул Карфаген и отправился воевать с маврами.

В конце августа византийский флот спокойно пристал к африканскому берегу в заливе Малый Сирт (современный Габес), к югу от Карфагена. Войска сошли на берег и сразу же, ведомые Велизарием, двинулись к столице вандалов.

Столичным гарнизоном командовал брат короля — Аммата. По приказу Гелимера он убил плененного Гильдерика и часть его сторонников, а потом выступил со своей армией по направлению к городу Дециму, расположенному в десяти милях к югу от стен Карфагена. План короля предусматривал, что здесь вандалы атакуют корпус Велизария сразу с трех сторон: с фронта Аммата, с тыла — сам Гелимер, а со стороны суши, с левого фланга — отряды его племянника Гибамунда. Эта одновременная круговая атака должна была состояться 13 сентября.

План, как это чаще всего и бывает с военными планами, сам по себе был хорош, но выполнение его оставляло желать лучшего. Аммата то ли прибыл слишком рано, то ли у него просто сдали нервы. Он ввязался в бой с передовым отрядом византийцев и погиб, а его людей византийцы загнали под самые стены Карфагена. Уничтожен был и отряд Гибамунда, случайно наткнувшийся всего лишь на несколько сот болгар. Но самому Гелимеру сопутствовал успех: он нанес тяжелое поражение коннице Велизария. И если бы он сразу бросился за отступавшими в погоню, он бы полностью разбил армию императора — и этим изменил бы ход истории.

Тем временем вандалы обнаружили на поле битвы тело Амматы, погибшего за несколько часов до этого. Король остановился, чтобы оплакать любимого брата. Эта передышка (скорее всего, не столь уж и долгая) позволила Велизарию собрать и перегруппировать свои войска. Он снова смело повел их вперед и абсолютно неожиданно обрушился на ничего не подозревавших вандалов, уже уверенных в своей победе. Совершенно не готовые к битве, они бросились врассыпную, и не к Карфагену, а в глубь страны. Воины Велизария гнались за ними до заката.

Таков был ход состоявшейся 13 сентября 533 года битвы под Децимом — одной из важнейших в мировой истории, хотя она и не принадлежит к числу широко известных.

На следующий день византийский флот уже вошел в залив, именуемый Тунисским, а 15 сентября Велизарий, доброжелательно приветствуемый населением, торжественно вступил в Карфаген — столицу вандалов, самый крупный город Северной Африки. Его ждал пир, который за два дня до этого повелел приготовить для себя Гелимер, не сомневавшийся, что вернется победителем.

Вся мощь народа, нанесшего Риму столько поражений и причинившего ему столько страданий, была уничтожена одним ударом. Карфаген снова был под властью императора — наследника традиций и славы римских цезарей.

Но этот огромный успех еще не означал конца войны. Гелимер все еще обладал серьезными силами, а население, уже успевшее привыкнуть к жизни под властью вандалов, относилось к византийцам по-разному. В самой столице, где Велизарий поддерживал жесткую дисциплину, отношение горожан было дружелюбным, а в сельской местности случались и нападения на солдат императора. Здесь считались с тем, что бывшие хозяева еще могут вернуться, а новых попросту боялись, к тому же вандалы платили за принесенные им головы убитых захватчиков. Что касается мавров, то многие их князья слали к Велизарию свои посольства, но некоторые заняли выжидательную и даже явно враждебную позицию.