朱古达战争（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）的一支罗马士兵队伍遭到伏击，几乎全军覆没。
驻军指挥官提图斯·图尔皮利乌斯·西拉努斯（titus turpilius Silanus），梅泰卢斯的下属，毫发无损地逃跑了。
据称，马略要求梅泰卢斯以胆怯罪判处西拉努斯死刑，但随后又攻击梅泰卢斯，认为这个判决过于严厉不符合量刑尺度。
马略还向罗马发信，声称梅泰卢斯已对于他的无限权力产生了迷恋。
梅泰卢斯警惕这个日益不满和愤恨的下属，允许马略返回罗马。
他回来的时间刚好够参加执政官选举；回来的时间足够他有效地进行选举拉票。
随着迅速战胜朱古达的政治压力越来越大，以及骑士阶层对元老院处理战争的不满下，马略在公元前107年当选为执政官。
他与卢修斯·卡西乌斯·朗吉努斯（Lucius cassius Longinus）一起针对梅泰卢斯在对抗朱古达时表现出的行动迟缓表示反对。
但元老院延长了梅泰卢斯在努米底亚的指挥权，从而阻止马略接管指挥。
马略说服他的盟友、当时的民众法官提图斯·曼利乌斯·曼基努斯（titus manlius mancinus）使公民大会（concilium plebis）推翻元老院的决定，给予他指挥权，从而绕过了这一限制。
梅泰卢斯拒绝亲自将指挥权移交给马略并返回罗马。
回到罗马后，元老院授予梅泰卢斯凯旋式，并给予他“努米底卡斯”（Numidicus）称号。
---
为了增强努米底亚地区的军队并赢得他所承诺的快速胜利，马略发现从罗马的传统人力来源，即拥有财产的男性中招募士兵非常困难。
除了在紧急情况下，罗马中期的常规做法是只允许拥有财产的公民入伍。
这可能与提比略·格拉古（tiberius Gracchus）的改革有关，后者通过让更多的人拥有更多土地，使更多的男性符合入伍资格。
尽管元老院允许马略正常征兵，他更倾向于请求志愿者，特别是退役老兵（evocati），并承诺胜利和战利品。
他还从没有财产的男性，即头税公民（capite censi）中招募志愿者。
随着更多士兵在意大利南部集结，马略启程前往非洲，将他的骑兵交给他新选举的财务官卢基乌斯·科尔内利乌斯·苏拉·菲利克斯（Lucius cornelius Sulla Felix）指挥。
马略发现结束战争比他之前所夸口的要困难得多。
朱古达正在进行游击战，而看起来没有比梅泰卢斯采取的战略更有效，即拒绝朱古达获得当地的增援和支持。
马略在公元前107年相对较晚地到达，但仍然在奇尔塔（cirta，现代的阿尔及利亚的康斯坦丁）附近打了一场胜仗。
在107年末，他通过一次危险的沙漠行军出其不意地抵达位于南方的卡普萨（capsa），在该城投降后，他杀死了所有成年男性，将幸存者奴役，并夷平了这座城市，将战利品分给他的士兵。
保持压力，马略将朱古达的军队驱逐到南方和西方进入毛里塔尼亚（mauretania）。
马略原本对接收放荡不羁的卢基乌斯·科尔内利乌斯·苏拉·菲利克斯作为他的财务官感到不满，但苏拉却是一名非常称职的军官，深受士兵们的喜爱。
与此同时，朱古达试图让他的岳父毛里塔尼亚国王博克斯（bocchus）加入他与罗马人的战争。
公元前106年，马略将他的军队远征西方，攻占了摩洛卡斯河（molochath）附近的一座堡垒。
不幸的是，这次推进使他接近博克斯的领土，最终激怒了这位毛里塔尼亚国王。
在塞里夫（Serif）以西的沙漠中，马略遭到一支由两个敌国国王指挥的努米底亚人和毛里塔尼亚人的联合军队出其不意攻击。
马略这次没有做好准备，在混战中，他所能做的只是形成防御圈。
毛里塔尼亚和盖图利亚（Gaetulian）的骑兵发起了攻击，一时间，马略和他的主力被围困在一座山上，而苏拉和他的部队则在附近的另一座山上处于防御状态。
罗马人设法抵挡住敌人的攻击直到傍晚，非洲人随即退去。
第二天清晨，罗马人突袭了非洲人防守不足的营地，彻底击溃了努米底亚-毛里塔尼亚联军。
马略随后向东进军，返回奇尔塔度过冬季。
非洲国王用轻骑兵骚扰其撤退，但被马略任命负责骑兵指挥的苏拉击退。
此时显然，罗马无法通过军事手段击败朱古达的游击战术。
因此，马略恢复了与博克斯的谈判，尽管博克斯已参与战斗，但尚未正式宣战。
最终，马略与博克斯达成协议，苏拉作为博克斯朝廷中的朋友，将进入博克斯的营地接收朱古达作为人质。
尽管博克斯可能会背叛，苏拉仍同意。
朱古达的剩余追随者遭到屠杀，他本人则被博克斯锁链带交给苏拉。
在随后的结果中，博克斯吞并了朱古达王国的西部，并被认定为罗马的盟友。
朱古达被扔进罗马的地下监狱（tullianum），最终在公元前104年参加马略的凯旋式后死去。
在凯旋式后，苏拉和马略就谁应该因抓获朱古达而获得荣誉发生争执。
由于苏拉作为马略的下属，按照罗马的传统，荣誉应该归马略。
然而，苏拉和他的贵族盟友则专注于对苏拉直接责任的强调，以抹黑马略的胜利。
根据普卢塔克（plutarch）的说法，这就是他们“不可治愈的仇恨”的“第一颗种子”。