朱古达战争（Jugurthine War）始于公元前112年，原因是“罗马人对朱古达（Jugurtha）野心的愤怒”，朱古达是一位努米底亚国王，他杀死了自己的同父异母兄弟，在与他们的内战中屠杀意大利人，并贿赂许多显赫的罗马人以获得在元老院的支持。
在敌对行动开始后，第一支被派往努米底亚的军队显然被贿赂以撤回，第二支军队则被击败并被迫屈服于耻辱之下。
这些失败削弱了人们对贵族在处理外交事务时能力的信任。
虽然马略在担任民众法官和执政官期间似乎与梅泰利家族（Caecilii Metelli）决裂，但梅泰利家族并没有因为这一破裂而对他产生很大的成见。
公元前109年，马略为了提高自己当选执政官的机会，加入了当时的执政官昆图斯·凯基利乌斯·梅泰卢斯（Quintus Caecilius Metellus），参与了他对朱古达的征战。
在萨卢斯（Sallust）对梅泰卢斯战役的详细记载中，没有提到其他副将，因此马略可能是梅泰卢斯的高级部下和得力助手。
梅泰卢斯利用马略的强大军事经验，而马略则在为自己争取执政官的机会。
在穆图尔河战役（Battle of the Muthul）中，马略的行动拯救了梅泰卢斯的军队免于灭亡。
朱古达切断了罗马人通往穆图尔河（River Muthul）的通路，而他们希望在那里补充水源。
罗马人不得不在沙漠中与朱古达作战，在这里努米底亚轻骑兵占据优势。
努米底亚骑兵将罗马军队分散为小分队，并迅速控制了战场。
每个罗马小组都在独立为生存而战。
这时，马略重新组织了一些分队，率领2000名士兵穿越努米底亚人，与梅泰卢斯会合。随后，他们带领军队对抗占据高地的努米底亚步兵。
在控制高地后，马略和梅泰卢斯带领部队向努米底亚骑兵的后方发起攻击。
罗马人获得了主动权，努米底亚人别无选择，只能撤退。
---
到公元前108年，马略表达了他竞选执政官的愿望。
梅泰卢斯（Metellus）并没有同意马略返回罗马， 建议他等到梅泰卢斯的儿子当选（当时他只有20岁，意味着要等上几十年）。