当时，努米底亚国王米奇普萨死后不到一年，对王权“三分割”不满的两个亲儿子和养子朱古达起了纷争，继承人之间的争斗，转瞬间演变为国家的内乱。刚一交锋，胜负立分，胜者是养子朱古达。米奇普萨国王的两个亲儿子一个战死，另一个叫阿泰鲁马雷的被追得走投无路，只好跑到罗马去求助。公元前112年，罗马对朱古达宣战。

第二年，即公元前111年，罗马军登陆北非，然而等待大军的不是朱古达率领的努米底亚部队，而是朱古达派来的投降使者。使者表达了朱古达的投降条件，只要罗马认可他的努米底亚国王王位，他就愿意臣服并继续保持在罗马霸权之下的同盟关系。率领罗马军队的执政官贝斯蒂亚接受了朱古达的投降申请。作为讲和的条件，要求朱古达本人拜访罗马阵营，投降文件签署之后，贝斯蒂亚就率大军从非洲回国。

然而，朱古达又犯了一个错误，他派人在罗马暗杀了一个相当于他的堂兄弟的人物，暗杀成功了，凶手却被抓住了。罗马人最讨厌鬼鬼崇崇在背后搞暗杀的行径，于是再度掀起镇压朱古达的舆论。第二年（前110），罗马再次把军队开到了非洲。

这回迎接罗马军队的，是全副武装的努米底亚士兵，因出乎意料而准备不足的罗马军很快即被包围。罗马军陷入两难处境，要么全军战死，要么接受朱古达提出的停战条件---解除武装，10日内退出非洲。罗马军被迫选择了后者，在屈辱的状态下回到了罗马。骑虎难下的罗马，这回决意认真对待与死敌朱古达的战争。这回担任罗马军总指挥的，是已选出的公元前109年度的执政官昆图斯.凯奇利乌斯.梅特鲁斯。为司令官梅特鲁斯配的副将，是虽无高贵出身但属久经历练型人才的佼佼者---时年48岁的盖乌斯.马略。

公元前109年夏，从原迦太基领土向西边的努米底亚进军的梅特鲁斯部队，在与努米底亚境内迎敌的朱古达军队之间，爆发了第一场战斗。梅特鲁斯率步兵，副将马略率骑兵投入战斗，这一仗以罗马的胜利而告终。朱古达混在四处逃窜的己方士兵中得以逃脱。梅特鲁斯并不穷追朱古达，他的谋略是把周边一带的部落拉拢到自己这一边来，以使逃散的朱古达军难以重新集结。

为了尽早与朱古达决战，也为了防止朱古达打游击战，梅特鲁斯把军队分为两部分：第一军由自己指挥，第二军由马略指挥。这个战术大体上是成功的。第二年（前108）开始的会战，朱古达又被打败逃跑了。然而，这个战术的不利之处是不能尽快对朱古达实行决定性的打击，战争有被拖长的迹象。

副将马略劝说上司梅特鲁斯改变战术，但梅特鲁斯听不进去。限于自己不掌握总指挥权，不能够按照自己的意图打仗，又担心拖延下去会使自己和士兵们困在非洲，马略决心自己竞选执政官。在罗马召开的公民大会上，马略不仅明确表达了当选执政官志在必得的态度，而且还要和选民订立明确的公约---生擒朱古达，拉回罗马处决，早日终结朱古达战争。

公元前108年末，公民大会的气氛对平民候选人马略十分有利。这五六年罗马军的战绩，苦战已成为常态，就连保持苦战不败都很难做到。在马其顿，执政官加图率领的军队被从北方入侵的色雷斯人打败。在欧洲，执政官卡尔波涅斯率领军队抗击从北欧入侵的蛮族，首战即负。更不能容忍的是在非洲，执政官率领的罗马军，竟打不过对手朱古达，屈辱地缴械讲和才得以逃脱。

公民大会不仅选举没有任何背景的“新人”马略为公元前107年度的执政官，而且通过决议由马略负责非洲军事。执政官马略在行使自己组建正规军团的权力时，将历来的征兵制改为志愿兵制，由此罗马的兵役不再是公民的义务，而成为了一种职业，响应马略召唤来当志愿兵的，大部分是失去了农地的失业者。根据马略的志愿兵体制创建的罗马军队，实质上成为职业军人集团。

虽说非洲战局没有马上改观，但擅长果敢速攻战法的马略总司令的到来还是给罗马军队带来了活力。无产阶级的志愿兵们作战更为勇敢，罗马军相继攻占了朱古达实行游击战的众多基地。当年深秋时节，罗马军已控制了努米底亚的一半国土。但朱古达还健在，战争还未结束，即将结束的却是马略的执政官任期。

于是马略向公民大会提出要求，如果非洲战事要继续进行，就要给予他绝对的军事指挥权。公民大会通过了给他的继续授权，第二年，即公元前106年，马略能够继续在非洲指挥军队。然而日益明确的现实是，要想结束朱古达战争，仅靠战斗的胜利还不够。而马略擅长的果敢速攻战法，也由于朱古达基地太多，东躲西藏而难以奏效。

如果不能切断朱古达与其最大同盟者毛里塔尼亚国王的关系，完全孤立朱古达也是不可能的。要想孤立朱古达，外交上的才能比军事上的能力更为重要。马略对外交并不擅长，需要给他配备一个具备外交才能的助手，于是路奇乌斯.科尔涅利乌斯.苏拉从罗马来到了非洲战争前线。罗马史上另一个主人公登场了，那一年，苏拉年仅32岁。