En été 428, Boniface envoie un ami sûr au camp de Gonderic, roi des Vandales, pour des négociations secrètes. Plus de vingt ans avant, dans la nuit du 31 décembre 406 au 1 janvier 407, des dizaines de milliers de Vandales, Suèves, Burgondes, Hérules et Alains ont franchi le Rhin gelé par un froid exceptionnel. Ils ont ravagé la Gaule, traversé les Pyrénées et se sont installés en Espagne qu’ils se sont partagée.

Le comte Boniface propose à Gonderic une alliance et lui offre l’établissement de son peuple en Afrique et une solde à ses guerriers. Mais Gonderic meurt bientôt et les négociations continuent avec son frère Genseric, le nouveau roi des Vandales. Celui-ci de petite taille et boite d’une jambe à la suite d’une chute de cheval. Cruel et coléreux, il déteste le luxe, a de grandes ambitions et savait saisir les moments opportuns.

Lent et circonspect, Genseric répond aux propositions de l’envoyé de Boniface :

- Vous dites que le compte Boniface nous propose des terres en Afrique et la solde aux guerriers pour un service loyal. Mais là-bas, il fait terriblement chaud ! Nous sommes nés en froide Germanie.

Impossible de deviner ses pensées réelles. Le roi continue :

- Par conséquent, le salaire des guerriers dans ce climat dur pour eux doit être élevé. En plus, je comprends bien que n’est pas exclu un conflit avec Galla Placidia. En fait, vous nous invitez à soutenir une insurrection. C’est très dangereux. Il faut donc prévoir une rénumération supplémentaire pour le risque ...

Après avoir discuté et réglé tous les détails, Boniface et Genseric ont ratifié leur traité d’alliance. Le roi est invité en Afrique avec les Vandales ses alliés alains, installés en Espagne. Au début de 429, les Espagnols, contents du départ des Vandales et des Alains, ont commencé à rassembler des bateaux pour assurer la traversée du détroit de Gibraltar. Boniface, lui aussi, a envoyé sa flotte.

En mai 429, les Vandales et les Alains débarquent en Afrique. Quelques jours après, Genseric fait la revue de son armée. Il n’avait que cinquante mille hommes effectifs. Le lendemain, le roi rassemble quatre-vingts officiers et les nomme chacun commandant de régiments de mille soldats. Après avoir divisé les guerriers entre ces officiers, Gengeric passe en boitant devant leur groupe et déclare :

- Je vous ordonne d’engager des soldats supplémentaires dans vos détachements afin de porter leur nombre à mille guerriers. Vous êtes autorisés à mobiliser même des vieillards, des adolescents et des esclaves.

Pensif, il s’arrête et caresse sa barbe rousse. Alors, un des officiers sort du rang et dit :

- Nous sommes abordés par les donatistes qui sont persécutés par les autorités et ont perdu tous leurs droits de citoyens. On confisque leurs biens, on les punit par des amendes. Dans ces circonstances, les donatistes nous regardent comme des libérateurs et veulent ardemment servir dans notre armée. Dans les montagnes, se cachent leur groupes armés qui continuent d’exercer leurs rites.

Genseric se réjouit :

- Parfait ! Je vous autorise à les engager, surtout les anciens soldats et leurs résistants armés.

Encouragé, le deuxième officier dit :

- Les Maures sont très curieux. Des villages voisins et des monts Atlas ils viennent visiter notre camp. Ces Maures ont l’air guerrier et regardent avec grand intérêt nos armes et nos vêtements. Certains parlent latin et se disent prêts à se battre contre les Romains, leurs oppresseurs.

Cette fois Genseric est complètement ravi :

- Commencez à les engager dans vos détachements. Par la suite, nous créerons une armée auxiliaire composée de guerriers maures.

Il lève ses poings vers le ciel :

- L’Afrique attendait les Vandales !