atas upayanya, belisarius dihargai oleh justinian dengan komando ekspedisi darat dan laut melawan kerajaan vandal, yang dipasang pada 533-534.
orang-orang romawi memiliki alasan politik, religius dan strategis untuk kampanye semacam itu.
perompak perusak pro-romawi, hilderic, telah digulingkan dan dibunuh oleh perampas gelimer, yang memberi alasan kepada justinianus secara hukum.
orang-orang veteran arian telah secara berkala menganiaya orang-orang kristen nicea di dalam kerajaan mereka, yang banyak di antaranya menuju ke konstantinopel untuk mencari ganti rugi.
para vandal telah meluncurkan banyak serangan bajak laut mengenai kepentingan perdagangan romawi, menyakiti perdagangan di wilayah barat kekaisaran.
justinianus juga ingin menguasai wilayah vandal di afrika utara, yang merupakan salah satu provinsi terkaya dan keranjang roti dari kekaisaran romawi barat dan sekarang sangat penting untuk menjamin akses romawi ke mediterania barat.
pada akhir musim panas 533, belisarius berlayar ke afrika dan mendarat di dekat caput vada (dekat chebba di pantai tunisia).
dia memerintahkan armadanya untuk tidak melupakan tentara, lalu berjalan di sepanjang jalan raya pesisir menuju ibu kota perusak kartago.
dia melakukan ini untuk mencegah agar persediaan tidak terputus dan untuk menghindari kekalahan besar seperti yang terjadi selama usaha basiliscus untuk merebut kembali afrika utara 65 tahun sebelumnya, yang telah berakhir pada bencana romawi pada pertempuran cap bon pada tahun 468.
sepuluh mil dari kartago, kekuatan gelimer (yang baru saja mengeksekusi hilderic) dan belisarius bertemu di battle of ad decimum pada tanggal 13 september 533.
ini hampir berubah menjadi kekalahan bagi orang romawi; gelimer telah memilih posisinya dengan baik dan berhasil melewati jalan utama.
orang-orang romawi tampak dominan di kedua sisi jalan utama menuju kartago.
pada puncak pertempuran, gelimer menjadi bingung saat mengetahui kematian saudaranya dalam pertempuran.
hal ini memberi belisarius kesempatan untuk berkumpul kembali dan dia terus memenangkan pertempuran dan merebut kartago.
kemenangan kedua dalam pertempuran tricamarum pada tanggal 15 desember, mengakibatkan penyerahan gelimer di awal tahun 534 di gunung papua, memulihkan provinsi romawi utara afrika yang hilang ke kekaisaran.
untuk prestasi ini, belisarius diberi kemenangan romawi (yang terakhir diberikan) saat kembali ke konstantinopel.
menurut procopius dalam prosesi tersebut diarak rampasan bait suci yerusalem (harta perusak, termasuk banyak benda yang dijarah dari roma 80 tahun sebelumnya, regalia kekaisaran dan menorah kuil kedua di antara mereka) yang telah ditemukan dari perampokan modal bersama dengan gelimer sendiri sebelum dia dikirim ke pengasingan yang damai.
medali dicap untuk menghormatinya dengan tulisan gloria romanorum, meski sepertinya tidak ada yang bertahan sampai zaman modern.
belisarius juga menjadi satu-satunya konsul pada tahun 535, menjadi salah satu orang terakhir yang memegang jabatan ini, yang berasal dari republik romawi kuno.
pemulihan afrika tidak lengkap; pemberontakan tentara dan pemberontakan oleh berber asli melanda prefektur praetoria yang baru di afrika selama hampir 15 tahun.