朱古达战争（Jugurthine War）始于公元前112年，原因是“罗马人对朱古达（Jugurtha）野心的愤怒”，朱古达是一位努米底亚国王，他杀死了自己的同父异母兄弟，在与他们的内战中屠杀意大利人，并贿赂许多显赫的罗马人以获得在元老院的支持。

在敌对行动开始后，第一支被派往努米底亚的军队显然被贿赂以撤回，第二支军队则被击败并被迫屈服于耻辱之下。

这些失败削弱了人们对贵族在处理外交事务时能力的信任。

虽然马略在担任民众法官和执政官期间似乎与梅泰利家族（Caecilii Metelli）决裂，但梅泰利家族并没有因为这一破裂而对他产生很大的成见。

公元前109年，马略为了提高自己当选执政官的机会，加入了当时的执政官昆图斯·凯基利乌斯·梅泰卢斯（Quintus Caecilius Metellus），参与了他对朱古达的征战。

在萨卢斯（Sallust）对梅泰卢斯战役的详细记载中，没有提到其他副将，因此马略可能是梅泰卢斯的高级部下和得力助手。

梅泰卢斯利用马略的强大军事经验，而马略则在为自己争取执政官的机会。

在穆图尔河战役（Battle of the Muthul）中，马略的行动拯救了梅泰卢斯的军队免于灭亡。

朱古达切断了罗马人通往穆图尔河（River Muthul）的通路，而他们希望在那里补充水源。

罗马人不得不在沙漠中与朱古达作战，在这里努米底亚轻骑兵占据优势。

努米底亚骑兵将罗马军队分散为小分队，并迅速控制了战场。

每个罗马小组都在独立为生存而战。

这时，马略重新组织了一些分队，率领2000名士兵穿越努米底亚人，与梅泰卢斯会合。随后，他们带领军队对抗占据高地的努米底亚步兵。

在控制高地后，马略和梅泰卢斯带领部队向努米底亚骑兵的后方发起攻击。

罗马人获得了主动权，努米底亚人别无选择，只能撤退。

---

到公元前108年，马略表达了他竞选执政官的愿望。

梅泰卢斯（Metellus）并没有同意马略返回罗马， 建议他等到梅泰卢斯的儿子当选（当时他只有20岁，意味着要等上几十年）。

尽管如此，马略开始为执政官职位进行竞选。

萨卢斯（Sallust）声称，这在某种程度上是受到乌提卡（Utica）一位算命师的启发，该算命师“宣称他将拥有伟大而非凡的事业。因此，预言者建议他相信神灵，去实现自己的计划，并尽可能多地去测试自己的运气，预测他的所有事业都会有一个幸福的结局”。

马略很快通过对士兵的态度赢得了他们的尊重，他与士兵们一起吃饭，并证明自己不怕与他们共同承担任何工作。

他还声称可以在几天内用梅泰卢斯一半的军队抓住朱古达（Jugurtha）来赢得意大利商人的支持。

这两组人都写信赞扬他，暗示他可以快速结束战争，而不像梅泰卢斯那样采取稳扎稳打的乡村征服策略。

在公元前109年和108年冬季，驻守瓦加（Vaga）的一支罗马士兵队伍遭到伏击，几乎全军覆没。