Велисарий немедленно отплыл на юг и после непродолжительной стоянки на Мальте высадился в бухте примерно в пяти днях пути к востоку от Карфагена. Отсюда войска двинулись на запад по суше старыми римскими дорогами, а корабли поплыли туда же вдоль побережья.
Прокопий в «Войне с вандалами» упоминает о письме императора, в котором тот оправдывал свои действия узурпацией Гелимером власти. «В тот же день попечитель государственной почты перешел на сторону римлян, передав им всех казенных лошадей. Был захвачен также один из тех, кого отправляют с царскими посланиями и кого называют „вередариями“. Стратиг не сделал ему никакого зла, но, одарив большим количеством золота и получив от него обещание верности, вручил ему письмо, которое василевс Юстиниан написал вандалам, для того чтобы он передал его вандальским архонтам. Письмо это гласило следующее: „У нас нет намерения воевать с вандалами, и мы не нарушаем заключенного с Гизерихом договора, но мы хотим свергнуть вашего тирана, который, презрев завещание Гизериха, заковал вашего царя в оковы и держит в тюрьме; который одних из ненавидимых им родственников сразу же убил, у других же отнял зрение и держит под стражей, не позволяя им со смертью прекратить свои несчастия. Итак, соединитесь с нами и освободитесь от негодной тирании для того, чтобы вы могли наслаждаться миром и свободой. В том, что это будет предоставлено вам, мы клянемся именем Бога“. Таково было содержание письма василевса. Получив его от Велисария, вередарий не решился сообщать о нем открыто, но тайно показал его своим друзьям и в сущности не сделал ничего, что имело бы какое-либо значение»[303]. Судя по последней реплике, никакого письма не существовало: историк пытался оправдать действия Юстиниана и одновременно объяснить, почему о столь важном факте, как объявление войны, вандалы не узнали.
Поскольку Африку надлежало присоединить к империи, а не разорить, Велисарий держал армию в строгости: не позволял мародерствовать и строго наказывал тех, кто покушался хотя бы на фрукты в саду частного лица. Благодаря этому он «настолько привлек на свою сторону ливийцев, что впредь шел по их стране как по своей собственной: жители этих мест не прятались от войска и не стремились что-нибудь скрыть, но охотно продавали продукты и оказывали солдатам всякого рода услуги. Проходили мы в день по восьмидесяти стадий и до самого прибытия в Карфаген останавливались на ночлег либо в городах, если это удавалось, либо в лагере, принимая меры предосторожности сообразно с обстоятельствами»[304].
В сентябре 533 года под Дециумом вандалы были разбиты. Один переход — и имперские отряды стояли уже перед обветшавшими стенами Карфагена, а в море колыхались сопровождавшие армию корабли. 13 сентября жители разомкнули цепь, закрывавшую городскую гавань Мандракий, и открыли ворота: город возвращался под власть римлян без сопротивления. Зимой 534 года под Трикамаром к западу от Карфагена Гелимер проиграл вторую битву. У него уже не было солдат, союзники-мавры тоже не поддержали его, и в марте 534 года вандальский король, загнанный куда-то в горы и окруженный, сдался, не выдержав мук голода. Сообщая об этом, Прокопий поведал историю, которая украсила бы любой западноевропейский рыцарский роман. Прячась в какой-то горной пещере, Гелимер послал Фаре, командиру византийского отряда, письмо с просьбой прислать ему каравай печеного хлеба, губку и кифару. Посланец объяснил недоумевающему Фаре суть этой странной просьбы: хлеба Гелимер не видел несколько месяцев, губка нужна ему, чтобы протереть воспалившийся глаз, а кифара — исполнить сочиненную им песню о своем несчастье. Фара расчувствовался и всё выслал — но осаду не ослабил, лишь усилил.