Одной из причин, побуждавших Византию покончить с бесперспективной войной, была и новая ситуация, складывавшаяся на Западе (в вандальском королевстве). В отличие от вестготов вандалы пришли в Северную Африку как прямые завоеватели, поэтому обращались с местным населением как с покоренным. Все надежды африканцев возлагались лишь на интервенцию Византии. Пренебречь этой ситуацией (при относительной немногочисленности вандалов и начавшихся восстаниях римского населения) было трудно. Успешная война могла стереть воспоминания о восстании Ника, приглушить внутренние противоречия, поднять престиж Юстиниана и разбудить уже начинавшие угасать надежды всех римлян Запада, мечтавших сбросить владычество варваров.
В июне 533 года к вандальскому побережью скрытно отплыла экспедиция во главе с Велисарием (16-тысячная армия на 500 судах), которой удалось внезапно высадиться недалеко от Карфагена. Не успевший собрать силы и прийти в себя от растерянности, Гелимер в битве при Трикамаре был наголову разгромлен и взят в плен. Потерявшие своего короля вандалы не смогли оказать сопротивления. При поддержке местного римского населения Вандальское королевство в 534 году перестало существовать (превратившись в византийскую префектуру). Это была первая и «величайшая» победа. Велисарию был устроен в Константинополе пышный триумф. Победителем же оказался Юстиниан, торжественно принявший титулы «вандальского» и «африканского». Эта победа внесла растерянность в варварские королевства, а Юстиниану и его окружению подарила надежду на возможность успешного раз грома остготов в Италии, освобождения Древнего Рима, столицы великой Римской империи.
Сразу же после завоевания Северной Африки было начато строительство системы пограничных укреплений. Обычная численность армии, которую удавалось собирать для крупных военных кампаний, не превышала 25 000- 50 000 человек, поэтому оборонительное строительство было совершенно оправдано. Оно позволяло защищать границу небольшими гарнизонами. Крепости и укрепления становились убежищами для местного населения, также включавшегося в оборону. Благодаря этой системе Византия могла иметь сравнительно небольшую мобильную армию. Но в отличие от тех районов, где подобно областям Запада, она имела существенную поддержку, Византия не могла одерживать решающих побед, поэтому дело обычно заканчивалось переговорами, компромиссом и выплатами.
В остготском королевстве разгром вандалов, естественно, оживил провизантийские силы, что привело к ответной консолидации остготской военной верхушки. Византийцы воспользовались убийством своих сторонников, королевы Амаласунты (дочери Теодориха), для того чтобы начать военные действия. В 534 году Велисарий высадился в Сицилии, и в течение нескольких месяцев эта житница Италии была очищена от остготов. Велисарий переправился в Италию, а в 536 году вступил в Рим.