ガイウス・マリウス
紀元前102年、マリウスは4度目の執政官に選出され、同僚執政官はクィントゥス・ルタティウス・カトゥルスであった。プルタルコスは、クィントゥス・セルトリウスが敵に潜入していたとするが、ゲルマン民族が接近していることは分かっていたようだ。彼らは、リグーリア州から海沿いにイタリアへ侵入し、マリウスを攻撃するグループと、アルプスを大回りして北東から侵入するグループに分かれ、挟撃作戦を展開しようとしていたとプルタルコスは言うが、古代の行軍速度、しかも荷物と家族連れで可能だったかかなり怪しい。
この年、プラエトルのマルクス・マリウスが、恐らくヒスパニア・ウルテリオルに派遣され、ケルティベリア人の助けを受けてルシタニア(現ポルトガル)人に勝利している。
マリウスは無骨な人物であったとされ、プルタルコスはその姿を描いた石像も気性をうかがわせる風貌だったと書き残している。上流階層が嗜んだギリシア文化には興味を示さなかったが、野心や矜持の点では彼らと同じ物を持っていた
紀元前134年、スキピオ・アエミリアヌス(小スキピオ)が執政官に選出された。長引くヌマンティア戦争の打開を元老院と人々に託され、特例での再選出であった。マリウスはこの遠征軍に加わり、翌前133年にかけて騎兵を務めたと考えられており、おそらくコルネリウス氏族のクリエンテス(庇護下にあるもの)だったのだろう。このスキピオの下で、マリウスはユグルタと共に訓練を受けた。厳格な軍隊生活を積極的に受け入れ、本人の眼前で敵との一騎打ちに勝利する事で小スキピオからの好意を勝ち取ったとされ、小スキピオは、あなたに何かあった場合、代わりになる者がいるかと聞かれた時、マリウスを指して「おそらくこの男だろう」と答えたといい、マリウスはそのことを死ぬまで大事な思い出としていたという。
マリウスはまだクルスス・ホノルム(名誉の階梯)の入り口に立ったばかりだったが、ローマのエクィテスである彼をヒスパニアの民が放っておくはずがなく、この地である程度のパトロネジ(庇護と報恩の関係)を築いた可能性が高い。シケリアのディオドロスは、マリウスをプブリカニ(入札によって徴税を代行する請負人)であったかのように書いているが、元老院議員は紀元前218年のクラウディウス法によって商売を実質禁止されており、その後のキャリアから考えればほぼありえない。
息子の小マリウスは、雄弁家クラッススの娘リキニアと結婚したが、彼については不明な点が多く、子供がいたかどうかはっきりとわからない。マリウスには姉妹がおり、キケロの祖父の義兄弟となるグラティディウスと結婚し、その子はマリウスの弟、マルクスの養子に入った。他に、甥のガイウス・ルシウスがおり、前104年にマリウスの下でトリブヌス・ミリトゥムを務めたが、若い兵士ともめ事を起こして殺されている。
それを知ったスッラは同僚ポンペイウス・ルフスと共に、同盟市戦争の残党が抵抗するノラを包囲していた軍団を掌握したが、その際ほぼ全ての士官が同行することを拒否しており、この時点では軍団兵の私兵化が完成していたとは言いがたい。アッピアノスによれば、マリウスに別の軍団を立ち上げるられると、自分たちが戦争のおこぼれに預かれなくなると考えて、兵士たちはスッラに従ったという。
マリウスは自分が軍団を掌握するため、スッラの元に親戚であるマルクス・グラティディウスらを派遣したものの、スッラは彼らを殺し、元老院からの使者も追い返してローママ市へ急進、マリウスに迎撃のための時間的余裕を与えなかったが、エスクイリーナ門から侵入したところで市民の激しい抵抗に遭い、街に火を放った。エスクイリヌスの丘で抵抗を続けていたマリウスは、別働隊に背後を突かれそうになったため退却した。マリウスは市民、騎士、元老院議員らを動員する一方で奴隷に自由と引き換えに戦う事を要求したが、これに応えたのはわずか3人だったとされ、スッラに対抗できずにローマから脱出するに至った。
ローマを占領したスッラはすぐに元老院を召集し、スルピキウスの法を破棄してマリウス親子ら12人に「公敵」宣言を行い、翌年の執政官を選挙で決めると、ミトリダテス戦争へと向かった。元老院では年老いたスカエウォラ・アウグルただ一人が、スッラの脅しにも屈せず、ローマとイタリアを守ったマリウスを公敵とすることに反対したという。スカエウォラ・アウグルは、雄弁家クラッススの義父であった。ルキウス・コルネリウス・キンナとグナエウス・オクタウィウスが紀元前87年の執政官となった。
紀元前106年、帰国したメテッルス・ヌミディクスは、ヌミディアとユグルタに対する凱旋式を挙行し、ヌミディクスのコグノーメン(添え名)を得ている。ウェッレイウス・パテルクルスは、戦争はヌミディクスによって実質的に終わっていたとしている。
再開された戦争でマリウスはヌミディア軍を再び打ち破ったが、ユグルタは岳父であるマウレタニア王ボックスの支援を取り付けて各地での抵抗を続けた。マリウスはヌミディア王国の再南端にあるカプサを攻め落とし、遠隔地での反乱を防ぐ為に全ての成人男子を処刑した。さらにヌミディアとマウタレニアとの境にある要塞を攻め落とすなど強行軍を続け、時には攻撃を躊躇していた要塞への抜け道が偶然発見されるような幸運にも恵まれたが、軍事的勝利だけでユグルタを屈服させる事は困難であった。マリウスはキルタ付近で冬営を決め、スッラにボックス王との交渉を任せた。プルタルコスによれば、スッラは一度は人質にされる窮地に陥ったものの、最終的にはボックスを説得してユグルタを引き渡させた。
翌紀元前105年、ユグルタを捕らえたことで戦争を終結させたマリウスはローマへ帰還したが、既に翌年の執政官に選出されていた。プルタルコスは、このユグルタ戦争終結の功績を巡って、凱旋式を挙行したマリウスと、陰の立て役者である自分を誇示するスッラとの間で、敵意が芽生え始めたことを記している。
ユグルタ戦争での勝利によってマリウスは将軍としての名声を得たが、それはメテッルスの戦略を引き継ぎ、敵の裏切りや幸運を得た上での地道な努力による勝利であり、自身が公言していた程楽に勝利を挙げられた訳ではなかった。
この年の護民官の一人、プブリウス・スルピキウス・ルフス(英語版)は、新市民となったイタリック人と解放奴隷を、全35トリブス(選挙区、トリブス民会やプレプス民会の投票単位で、全市民がどこかに登録される)に登録する法案を提出した。反乱した同盟市に対し、ローマの指導層は市民権を付与することでローマ化させようとしていた。当初は新市民を、その影響力をなるべく削ぐために、全トリブスにではなく、限定して登録する予定だったところを、護民官ドルススの後継者ともみなされるスルピキウスが上記の提案をしたため暴動が起り、両執政官がローマを脱出、スルピキウスは更に、ミトリダテス戦争のインペリウムをマリウスに移すプレプス民会決議を行った。ベイディアンらは、新市民登録への反発が強かったことから、スルピキウスが後ろ盾を必要としてマリウスに近づいたのではないかと考えている。