Οι πολιτικές έριδες στο κράτος των Βανδάλων στη Βόρεια Αφρική έδωσε την ευκαιρία στον Ιουστινιανό να επιχειρήσει την Ανάκτηση της Αφρικής, την οποία πέτυχε. Οι προπαρασκευές για το εγχείρημα αυτό άρχισαν το καλοκαίρι του 532. Οι Βάνδαλοι της εποχής του Ιουστινιανού ήταν εκφυλισμένοι από την πολυτέλεια και την τρυφηλή ζωή. Η στρατιωτική τους πείρα πλέον περιοριζόταν στη διασφάλιση της γαλήνης και σε εξορμήσεις αντιποίνων εναντίον των Μαυρουσίων υπηκόων τους.
Η αντιρωμαϊκή και αντικαθολική πολιτική του Γελίμερα είχε ενώσει τους αστικούς πληθυσμούς εναντίον της βανδαλικής διοίκησης. Στην ύπαιθρο, όπου οι Βάνδαλοι γαιοκτήμονες μόνιμα εγκατεστημένοι στην πρωτεύουσα και στα μεγάλα κέντρα του κράτους ήταν λιγότερο πιεστικοί από τους Ρωμαίους, οι οποίοι ζούσαν στα κτήματά τους και όπου πολλοί από τους αγρότες ανήκαν στην εκκλησία των Δονατιστών, τα αντιβανδαλικά αισθήματα ήταν λιγότερα έντονα.
Τα φύλα των Μαυρουσίων, που κατείχαν τα εδάφη ως τον Ατλαντικό ωκεανό, συνδέονταν με ασταθή υποτέλεια με τους Βάνδαλους, ενώ παράλληλα συνέχιζαν τις εσωτερικές τους διενέξεις. Οι υπερπόντιες κτήσεις των Βανδάλων στην Σαρδηνία, την Κορσική και τις Βαλεαρίδες νήσους, προσέφεραν την απαραίτητη ξυλεία για τον βανδαλικό στόλο, και αντίστροφα έμεναν υποταγμένες λόγω της βανδαλικής ναυτικής δύναμης.
Ενώ το κύριο εκστρατευτικό σώμα συγκεντρωνόταν στην Κωνσταντινούπολη, η διπλωματία του Ιουστινιανού απέσπασε δύο προκαταρκτικές νίκες. Στην Τρίπολη, νπτιοανατικά του βανδαλικού κράτους, συνομωσία με επικεφαλής κάποιον Πουδέντιο ανάτρεψε τον Βάνδαλο διοικητή και κάλεσε τα βυζαντινά στρατεύματα από την Κυρηναϊκή να καταλάβουν την περιοχή. Οι δυνάμεις ήταν έτοιμες και διέσχισαν την έρημο με εκπληκτική ταχύτητα.Έτσι μια επαρχία του βανδαλικού κράτους ανασυνδέθηκε με το ρωμαϊκό κράτος την άνοιξη του 533.
Την ίδια περίπου εποχή στην Σαρδηνία κάποιος Γότθος, ο Γώδας, ηγήθηκε μιας ένοπλης επανάστασης. Ναυτική εκστρατεία υπό την ηγεσία του αδελφού του βασιλιά Γελίμερα στάλθηκε για να καταστείλει την επανάσταση στη νήσο. Έτσι ο τρομερός βανδαλικός στόλος και στρατός των 5.000 ανδρών καθηλώθηκε στα νερά της Σαρδηνίας το καλοκαίρι του 533.
Στο μεταξύ ο Βελισσάριος διορίστηκε αρχιστράτηγος της εκστρατευτικής δύναμης 18.000 ανδρών, 500 μεταγωγικών και 92 πολεμικών πλοίων. Συνοδευόταν από τον πρώην έπαρχο των πραιτορίων Αρχέλαο ως «έπαρχο του στρατοπέδου», δηλαδή υπεύθυνο του ανεφοδιασμού, από έναν Αλεξανδρέα ναύαρχο, τον Καλώνυμο, και από τον μετέπειτα ιστορικό Προκόπιο, ως στρατιωτικό γραμματέα, καθώς και από την σύζυγό του Αντωνίνα.
Σταθμεύοντας στην Ηράκλεια, στη Μεθώνη και την Ζάκυνθο, ο στόλος έφθασε στη Σικελία στα μέσα Αυγούστου. Η Σικελία αποτελούσε τμήμα του οστρογοτθικού βασιλείου και είχε ήδη διαφαλισθεί δαακίωμα διέλευσης από την αντιβασίλισσα Αμαλασούνθα. Ενώ ο στόλος ναυλοχούσε στα σικελικά ύδατα, ο Προκόπιος πέτυχε να έρθει σε επαφή στις Συρακούσες με κάποιον, που είχε φύγει από την Καρχηδόνα τρεις μέρες νωρίτερα και ο οποίος του ανέφερε ότι δεν είχε εκδηλωθεί καμιά ανησυχία στη βανδαλική πρωτεύουσα. Λίγες μέρες αργότερα ο στόλος απέπλευσε και αποφεύγοντας να πλησιάσει το βανδαλικό προπύγιο της Μελίτης (Μάλτας), προσέγγισε την αφρικανική ακτή στη Καπούτβαδα της Βυζακίας στα τέλη Αυγούστου. Αν έπλεε κατευθείαν εναντίον της Καρχηδόνας θα κινδύνευε να καταστραφεί επιχειρώντας απόβαση σε περιοχή που θα συναντούσε σθεναρή αντίσταση.
Όταν ο βασιλιάς Γελίμερ πληροφορήθηκε ότι ο ρωμαϊκός στόλος είχε αποβιβασθεί, βρισκόταν στο εσωτερικό της Βυζακίας. Αμέσως έστειλε εντολή στον αδελφό του Αμμάτα να θανατώσει τον Ιλδέριχο και τους οπαδούς του και να σπεύσει να ενωθεί με τον στρατό του νότια της Καρχηδόνας. Ο Βελισσάριος οδήγησε τον στρατό του βόρεια μέσω της παραλιακής οδού, ενώ ο στόλος ακολουθούσε κατά μήκος της ακτής. Τα σχέδια των Βανδάλων απέτυχαν και ο Αμμάτας συνάντησε τις ρωμαϊκές προφυλακές στο Δέκιμο, 15 περίπου χιλόμετρα νότια της Καρχηδόνας, προτού προλάβει ο στρατός του βασιλιά να φθάσει. Ηττήθηκε και σκοτώθηκε, ενώ τα υπολείμματα του στρατού καταδιώχθηκαν ως τα τείχη της Καρχηδόνας.
Ο Βελισσάριος και το ρωμαϊκό ιππικό βρέθηκαν λίγες ώρες αργότερα αντιμέτωποι με το ιππικό του βασιλιά Γελίμερα και κινδύνευε να ηττηθεί. Αλλά η θέα του πτώματος του αδελφού του στο πεδίο της μάχης καταρράκωσε το ηθικό του Γελίμερα και έδωσε το χρόνο στον Βελισσάριο να προωθήσει το πεζικό του. Μετά από μια σύντομη συμπλοκή οι Βάνδαλοι τράπηκαν σε φυγή δυτικά, προς τη Νουμιδία. Ήδη η Καρχηδόνα ήταν ανυπεράσπιστη.
Γεννάται το ερώτημα γιατί ο Γελίμερ δεν υποχώρησε εξ αρχής στην Καρχηδόνα, ώστε να αναγκάσει τον Βελισσάριο να αναλάβει μια δαπανηρή και αβέβαιη πολιορκία, που θα του έδινε τον χρόνο να ανακαλέσει τον στόλο του από τη Σαρδηνία. Η απάντηση είναι ότι οι Βάνδαλοι ένιωθαν τόσο ασφαλείς από ξένη επίθεση και τόσο αβέβαιοι για την πίστη των Ρωμαίων υπηκόων τους, ώστε δεν είχαν επισκευάσει ποτέ τα τείχη των αφρικανικών πόλεων, από τότε που τις κατέλαβαν, σχεδόν έναν αιώνα πριν. Τα τείχη της Καρχηδόνας ήταν ανεπισκεύαστα, με ρήγματα σε πολλά σημεία, έτσι η άμυνα της πόλης ήταν ανέφικτη.
Στις 14 Σεπτεμβρίου ο ρωμαϊκός στόλος περιέπλευσε το ακρωτήριο Μερκούριο και αγκυροβόλησε ανοιχτά της Καρχηδόνας. Όλη τη νύχτα η πόλη ήταν φωταγωγημένη και οι πολίτες υποδέχονταν τους νικητές με ζητωκραυγές από τα τείχη και τις προβλήτες. Οι ναύτες όμως φοβούνταν παγίδα και οπωσδήποτε είχαν εντολή να περιμένουν την άφιξη του αρχιστρατήγου. Το επόμενο πρωί ο Βελισσάριος εισερχόταν στην πρωτεύουσα της Αφρικής επικεφαλής των στρατευμάτων του, ανάμεσα σε επευφημίες των κατοίκων της. Οι στρατιώτες του είχαν διαταγές να μην βλάψουν τους πολίτες και να μην πάρουν ο,τιδήποτε χωρίς πληρωμή. Η μεταβίβαση της εξουσίας υπήρξε οαμλή. Οι υπόλοιποι Βάνδαλοι που είχαν καταφύγει στις εκκλησίες, τέθηκαν υπό στρατιωτική φρούρηση. Ο Βελισσάριος εγκατέστησε το στρατηγείο του στο ανάκτορο των Βανδάλων βασιλέων.
Πρώτη του μέριμνα ήταν να οχυρώσει την πόλη, γιατί θα μπορούσε σύντομα να βρεθεί πολιορκημένος από Βανδάλους. Ο Γελίμερ είχε ήδη ανακαλέσει τους 5.000 άνδρες από τη Σαρδηνία και κινήθηκε προς την Καρχηδόνα, προσπαθώντας να αποκόψει τα υδραγωγεία από τα οποία υδρευόταν η πόλη. Έστειλε επίσης πράκτορες στην πόλη για να επιχειρήσουν να προσεταιρισθούν τμήματα του πληθυσμού και του ρωμαϊκού στρατού. Ένα σώμα Βουλγάρων (Ούννων) άρχισε διαπραγματεύσεις μαζί του πράγμα που ανησύχησε τον Βελισσάριο. Ο τελευταίος εξαιτίας προφανώς του φόβου βανδαλικής διείσδυσης αποφάσισε να βγει από την Καρχηδόνα στα μέσα του χειμώνα και να δώσει μάχη εναντίον των Βανδάλων στο Τρικάμαρο, 30 χιλιόμετρα δυτικά της Καρχηδόνας. Οι Ρωμαίοι κατήγαγαν σημαντική νίκη. Ολόκληρος ο βανδαλικός στρατός έπεσε στο πεδίο της μάχης ή αιχμαλωτίστηκε και το στρατόπεδό του δηώθηκε.
Ο βασιλιάς Γελίμερ και λίγα μέλη της ακολουθίας του διέφυγαν στα δυσπρόσιτα ορεινά της ΝΔ Νουμιδίας, όπου γρήγορα αποκλείσθηκαν από ρωμαϊκή δύναμη. Στο τέλος Μαρτίου του 534 συνθηκολόγησε με αντάλλαγμα εγγυήσεις του Βελισσαρίου ότι δεν θα τον κακομεταχειριζόταν. Το κράτος των Βανδάλων είχε καταστραφεί. Ήδη πριν από την παράδοση του Γελίμερ, ο Βελισσάριος είχε στείλει αποσπάσματα να καταλάβουν στρατηγικά σημεία στη Νουμιδία και στη Μαυριτανία. Οι Βησιγότθοι της Ισπανίας έπρεπε να αποθαρρυνθούν για να μην επιχειρήσουν να επωφεληθούν από την κατάρρευση του βανδαλικού κράτους. Ναυτικές δυνάμεις στάλθηκαν για να καταλάβουν την Σαρδηνία, της Κορσική και τις Βαλεαρίδες νήσους.
Η είδηση της κατάληψης της Καρχηδόνας έφθασε πιθανότατα στην Κωνσταντινούπολη στις αρχές Οκτώβρη. Στο διάταγμα της δημοσίευσης των «Εισηγήσεων» ο Ιουστινιανός πρόσθεσε στα κενά του επίθετα του Αλαμαννικού, Γοτθικού, Φραγκού, Γερμανικού, Αντικού, που αποτελούσαν μέρος του αυτοκρατορικού του τίτλου, τους περισσότερο δικαιολογημένους τίτλους «Αλανικός», «Βανδαλικός» και «Αφρικανός». Ο τελευταίος αποτέλεσε ανάμνηση του Μεγάλου Σκιπίωνα του Αφρικανού, ο οποίος είχε κατακτήσει την Καρχηδόνα επτάμισι αιώνες παλαιότερα.
Ο πλήρης μηχανισμός της αυτοκρατορικής διοίκησης επανεγκαταστάθηκε σύντομα στην βόρεια Αφρική, μολονότι δεν είχαν περιέλθει όλες οι παλαιές επαρχίες στον απόλυτο έλεγχο του Βυζαντίου. Την ημέρα του θριάμβου ο Βελισάριος πεζός, ηγήθηκε πομπής από την κατοικία του στον Ιππόδρομο. Ακολούθηε ο Γέλιμερ και άλλοι αιχμάλωτοι και όλοι οι θησαυροί που είχε αρπάξει από τη Ρώμη ο Γιζέριχος το 455 και που τώρα έπεφταν σε ρωμαϊκά χέρια. Ο Βελισσάριος προσκύνησε μπροστά στον Ιουστινανό και την Θεοδώρα. Τον μιμήθηκε απρόθυμα ο Γελίμερ, μουρμουρίζοντας καθώς γονάτιζε «ματαιότης ματαιότητων, τα πάντα ματαιότης». Ο Ιουστινανός παραχώρησε στον Γελίμερα κτήματα στη μικρά Ασία όπου έζησε την υπόλοιπη ζωή του. Οι Βάνδαλοι στρατιώτες κατατάχθηκαν στον ρωμαϊκό στρατό και στάλθηκαν στο ανατολικό μέτωπο.
Ανάμεσα στα λάφυρα της Καρχηδόνας ήταν η επτάφωτη λυχνία, η Menorah, και άλλα κειμήλια του ναού, που είχε απαγάγει από τα Ιεροσόλυμα στη Ρώμη ο Τίτος το 70μ.Χ. και είχαν αργότερα μεταφερθεί από τη Ρώμη στην Καρχηδόνα από τον Γιζέριχο το 455. Μετά από αναγκαίες διαδικασίες εναποτέθηκαν σε εκκλησίες στα Ιεροσόλυμα, όπου και έμειναν μέχρι την άλωση της πόλης από τους Πέρσες το 614.
Ο Ιουστινιανός πρότεινε στον Βελισσάριο αν ήθελε να παραμείνει στην Αφρική ως αρχιστράτηγιος ή να επιστρέψει στην Κωνσταντινούπολη. Επέλεξε το δεύτερο γιατί οι εχθροί του διέδιδαν ότι σχεδίαζε να ιδρύσει μια ανεξάρτητη αυτοκρατορία στην Αφρική. Ο Ιουστινιανός του επέτρεψε να τελέσει θρίαμβο. Ο τελευταίος απλός πολίτης που είχε τελέσει θρίαμβο ήταν ο Λεύκιος Κορνήλιος Βάλβος, 550 χρόνια παλαιότερα επί Αυγούστου. Ο Βελισσάριος έλαβε και δεύτερη ανταμοιβή για τη νίκη του, την υπατεία για το έτος 535, και την 1η Ιανουαρίου αυτού του έτους εγκαινίασε την αρχή του με μια πομπή πρωτοφανή για ιδιώτη σε γενναιοδωρία και μεγαλοπρέπεια. Ο Ιουστινιανός είχε και άλλο, μεγαλύτερο έργο κατά νου για τον λαμπρό και πιστό του στρατηγό.
Με πληροφορίες από: Ιστορία του Ελληνικού Έθνους