由于边防压力和财政的限制，查士丁尼决定让贝利撒留的私兵为主的部队进攻汪达尔王国，再配以一定数量的蛮族雇佣军。如果贝利撒留能再次创造奇迹，自然是惠而不费的好事；如果失败，削弱的也只是贝利撒留的实力。

查士丁尼分配给贝利撒留的兵力仅有10,000名步兵和5,000名骑兵，除了贝利撒留的私兵之外，剩下的蛮族战士虽然单兵都具有良好的训练，但他们的忠诚也绝不可靠。在胜利时像野兽一样的凶猛，一旦失败，就可能反噬主人。

自西西里前往北非无疑最为便捷而易于补给。此时管理西西里岛的东哥特王国女领主阿玛娜·希莎正与汪达尔人交恶，由于527年汪达尔国王希尔德里克处死了她的姑母阿玛娜·伏妮塔，所以她保证东罗马远征军在西西里岛上将获得友好的接待。

希尔德里克此时已经被侄子格里梅尔推翻。J·F·C·富勒的《西方军事史》将格里梅尔描写为一个怯懦而无能的指挥官，这无疑是充满偏见的说法。格里梅尔骁勇善战，被誉为汪达尔王国的阿喀琉斯，他扭转了汪达尔王国和沙漠中活动的摩尔人作战时屡战屡败的局面，获得多次大胜，并让摩尔人为王国提供兵源。

533年6月22日，东罗马远征军在君士坦丁堡上船，共有500艘船（最大的载重750吨，最小的只有45吨），由两万名水手驾驶，有92艘快速的小战船护航，由两千名拜占廷奴隶划桨。

因为风向不利，他们在伯罗奔尼撒的梅多尼停留了很久，才达到了扎特，在那里又遇到飓风，花了十六天时间才到了西西里岛上的卡塔尼亚。

这一过程中，两个马萨格泰人在酗酒时杀死了一个向他们开玩笑的同伴，贝利萨留二话没说便将这两个马萨格泰人用尖木桩处死。他以严酷的军纪向蛮族们表明，即便是在军中骄横不法也要面临最严厉的惩罚，更不必说劫掠百姓。后来的事实证明，他的部下严格遵守了军纪、并因此收获了民心，这一点对于贝利萨留能快速征服北非作用颇大。

整个远征过程中由于路途遥远，贝利萨留必须要保证他的整只舰队在航行时不会出现掉队现象，因为在一个大舰队里尤其是在遇到暴风的时候，不可避免地会有许多船只会落在后面并且远离舰队。考虑到这个问题贝利萨留做了如下安排。他将他本人和他的随从乘坐的3艘船的帆从上面的角向下到整个帆的三分之一的地方全部涂成了红色，并且又让每只船在船头上挂上灯，以便能更好地将统帅的船分辨出来。随后他下令所有的船都跟在那三艘帆被涂红的船后面。并且一旦要起航的时候，都有喇叭发出信号，这样做的确很有成效，在那3艘船的率领下，整个舰队没有一艘船掉队。

汪达尔人有一支强大的舰队，如果贝利撒留的船队在中途被他们拦截，就可能会全军覆没。贝利撒留派自己的法律顾问——历史学家普罗柯比到叙拉古去，表面上装作购买粮食，实际上却尽量搜集情报。普罗柯比回来报告说，格里梅尔不知道这支远征军已经离开君士坦丁堡，而他的精兵正由其兄弟特查宗率领，在撒丁岛上镇压一个由查士丁尼煽动起来的叛乱。 显然，查士丁尼希望贝利撒留能在汪达尔王国精锐部队回师之前完成整场战役。

贝利撒留立即命令部队扬帆出海，一路经过马耳他和戈佐，在九月初望见非洲海岸，距从君士坦丁堡出发之日已经快三个月了，为了避免与汪达尔海军遭遇，贝利撒留不得不在远离迦太基城的地方上陆。

他在崩角以南130英里的卡普特瓦达登陆，受到当地人民欢迎，他建立了一个设防营地，到处散发查士丁尼的布告，说远征军只讨伐格里梅尔一人，绝非对人民作战。采摘田地里果子的士兵也遭到了贝利撒留的严惩，因为军纪如铁，利比亚人民纷纷箪食壶浆以迎王师。

拜占庭军队接着向北朝迦太基进发。他的前卫为300名骑兵，由副官约翰率领，另有600名匈人骑兵掩护他的左翼，而全部舰队则在他右面沿海岸行驶。海军紧跟陆军与陆军保持平行，避免被汪达尔人逐个击破。

9月13日，前卫到达阿德西姆隘路----从迦太基算起的第十个英里的里程碑。当听到敌军登陆的消息之后，格里梅尔的第一个意图就是设法拖延战争，以等待他的兄弟的精兵可以召回应战。同时他也痛恨他祖先的政策，把非洲城市的要塞工事全都拆毁了，以至迦太基处于无掩蔽的地位。此后，他又听到贝利撒留的兵力是如何渺小，于是命令在迦太基负责指挥的兄弟阿曼图斯，准备进攻入侵者。

即便罗马遗民并不欢迎汪达尔人的统治，但汪达尔王国除了本民族和阿兰人之外，还有着大量沙漠中的柏柏尔人战士可以雇佣，兵力上相对贝利撒留有绝对优势。但查士丁尼很可能没有考虑到这一点，误以为贝利撒留小小的部队只需要应对汪达尔王国统治阶层中征召的部队。

格里梅尔决定等敌人已经进入隘路之后，就从三个方向向敌人进攻。阿曼图斯从迦太基城出发，攻击敌人的前卫，辛巴穆德从西面越过山地攻击敌军左翼。

9月13日，阿曼图斯出了迦太基城，在其他两个纵队尚未就位之前就开始攻击，在战斗中他证明了他是一位勇敢的战士，他杀死12名贝利萨留的亲兵，但他本人也阵亡了，于是他的部队在恐惧中四散飞逃。贝利撒留的副官约翰率军趁势追杀一直追到迦太基城门口。

接着，辛巴穆德也带着2000精兵发动攻击，但又被匈人的侧卫击溃。等到这两支兵力都失败之后，格里梅尔还一点都不知道，由于在山地中迷失了方向，并未能打击在敌军主力的后背上。当他到达到阿曼图斯战死的地方，却与贝利撒留的先头部队遭遇，他将他们击败了，败兵纷纷逃走，向贝利萨留的主力部队那里跑去。

如果格里梅尔趁胜追击，或许能让贝利撒留亲自率领的前队遭遇败绩。但是他却因为看见自己兄弟的尸体感到悲痛，并且埋葬阿曼图斯而贻误战机。贝利萨留整顿了自己部队，当他收到阿曼图斯阵亡和约翰追击的消息后，他当机立断全速扑向没有准备的汪达尔军队，将其击溃，格里梅尔被迫撤往努米底亚。

《中世纪战争艺术史》的作者欧曼爵士认为，这场十里会战不过是机缘巧合下发生的无关紧要的几场小战。格里梅尔无法在山地中调动太多兵力，只能派遣少量精锐部队出动，希望能分进合击将贝利撒留拖长的队伍绞杀在群山当中。但在那个没有钟表的时代，格里梅尔并没有协调如此精妙作战计划的统筹才能。

如果贝利撒留的军队拥堵在狭隘的山道中，那么仅仅是先头部队战败就足以让整支部队陷入混乱。但实际情况时贝利撒留选择骑兵先行，步兵一直留在群山的后方。即便格里梅尔继续挺进，至多不过是迫使贝利撒留的试探性进攻结束而已。贝利撒留已经取得了利比亚地区的人心，仍能够重整旗鼓。

汪达尔人损失了一部分精锐部队，士气也受到影响，但实力尚存。真正的血战还在后方。

第二天，拜占廷的陆军进到迦太基城边，发现汪达尔部队大部分都已撤出该城。9月15日，城门打开，贝利撒留引兵入城，受到居民的欢迎。贝利撒留第一件事就是修补荒废的城防工事，希望用迦太基来作为一个香饵吸引盖利默来进攻，然后在以此消耗他的有生力量。

格里梅尔已经退到了一个叫作布拉里吉亚的地方，在迦太基城西约一百英里。在那里，他集合了更多的兵力，派人到撒丁去要求特查宗赶快前来支援。当特查宗到来之后，汪达尔最精锐的5000战士也回归到大部队当中。汪达尔人回师的速度，远远出乎查士丁尼和贝利撒留的预料。

汪达尔国王派人潜入迦太基，破坏了供给城内饮水的水道。格里梅尔知道贝利撒留部队中的匈奴人对他们服役的条件感到不满意，所以又派人去活动，使他们答应在下次战斗中倒戈攻击罗马人。以后，格里梅尔退往一个叫作特里卡梅伦的地方，距离迦太基大约只有十八英里，在那里建筑了一个设防营地，静候贝利撒留出击，计划用防御反击来避免初战不利导致的士气下降形成损害。

当贝利撒留得知他的匈奴部队不稳定之后，就用各种手段来笼络他们。最后结果是他们决定在下次会战中，不马上打击拜占廷军的后背，而是先采取观望态度，等看清楚哪方面获胜之后再动手。这一事件足以说明出来雇佣军的危险性，他们的惟一目标是抢劫，而胜利只不过是达到这个目的一种手段而已。

当他的匈奴部队暂时决定保守中立之后，贝利撒留决定奋勇进攻，用行动扼住命运的咽喉。既然敌人不会中计攻城，拖得越久对己方越不利。

他命令约翰率领1,500骑领先进发，第二天，大约是533年12月的中旬，贝利撒留率领他的全部步兵，连同剩余的500名骑兵，也向特里卡梅伦进军。由于匈奴人的不稳以及部分骑兵已经失去了他们的战马，贝利撒留的骑兵数量大大下降。

贝利撒留在左翼部署了自己的辅助部队，右翼部署了骑兵而在中央让约翰率领长枪兵和他的亲兵，以及统帅的军标。那天夜间，他在距离敌营相当远的地方宿营过夜。

当格里梅尔知道他来了之后，就向自己的部队训话说：宁可战死而不要使格里梅尔的荣誉蒙羞。大约在正午时候，他引兵挑战，突然前进到约翰的骑兵部队前面，那些人正在准备午餐。约翰迅速命令他的部下上马，把他们分为三个集团，自己指挥中央的兵力。贝利撒留也听到敌人进攻了，便把步兵留在后面，亲自率领500名骑兵赶来助战。此时，格里梅尔也把他的骑兵分为三个集团，由他的兄弟特查宗指挥中央的兵力。

贝利撒留希望将敌人引过河流，形成半渡而击的局势，但汪达尔人选择按兵不动。

约翰率领一小队经过挑选的精锐骑兵，越过夹在两军之间的一道溪流，向汪达尔人的中央部分冲锋，但马上被特查宗击败，约翰退回本阵之后，接着又进行第二次的突击，但仍被逐回。汪达尔人仅仅派出比罗马小股部队稍大一些的骑兵部队驱逐罗马骑兵，绝不渡河追击。

格里梅尔如此地小心谨慎，无疑是深知汪达尔骑兵单兵战斗力远不及拜占庭骑兵所致。他希望贝利撒留尽快率领主力骑兵发动拜占庭骑兵常常使用的鲁莽突进，然后发挥兵力优势进行围歼。

但如此的谨慎也难免使得己方士气低落，且忽略阵线的破绽。贝利撒留如汪达尔人所愿，率领将军卫队和约翰一同渡河，在喊声震天之中，发生了激烈的格斗。

早有准备的汪达尔人马上发起凶猛的围攻，给将军卫队造成了惊人的伤亡。贝利撒留是故意跳进对方的陷阱，自然早有预料。混战当中，约翰率领的最精锐那部分将军卫队已经瞄准了他的猎物。

随着一声骇人的尖啸，特查宗被砍倒落马，约翰完成了对敌人骑兵主将的斩首。这是拜占廷方面挥动全部骑兵进攻的信号，他们渡过溪流向敌军进攻。汪达尔人对拜占庭军全面进攻准备不足，他们包围贝利撒留的中军反而弱化了己方的侧翼，加上特查宗的战死，汪达尔人的两翼变得一击即溃。

敌军从中央部分开始崩溃，不久即全部溃散。这时，匈奴人看到罗马人获得了胜利，也就依照他们自己的约定，马上加入追击。汪达尔的骑兵全部被驱逐到他们的设防营地中，而拜占廷军也就马上开始洗劫死人身上的财物。 整场战斗在一个小时不到就宣布结束。

到黄昏将近时候，拜占廷的步兵才全数赶到，贝利撒留命令他们攻击敌人营寨。此时格里梅尔和他的军队早已因拜占庭军队鬼神般的战斗力而破胆，放弃营寨各自逃命，贝利撒留很轻松地大获得全胜。

第二天上午，贝利撒留命令约翰领兵追击，同时分兵接收新征服的土地。直到534年3月，在帕普斯山负隅顽抗的汪达尔王已经绝食度日时才投降。不久，贝利撒留凯旋归国。当贝利撒留离开非洲之后，穷凶极恶的税吏也来到了。在他们勒索之下，有许多已经与汪达尔妇女结婚的拜占廷人也都开始叛变。同时，当地的雅利安人因为被禁止不得为他们的孩子举行洗礼和进行一切宗教礼拜，所以也揭竿而起。接着在全面纷乱之中，摩尔人也乘机作乱，在这些收复的省区中扰乱蹂躏了三年以上的时间。

非洲的征服使查士丁尼有了一个良好的补给基地，便于向意大利方向作战。