Zwei Jahre danach führte er als Konsul Krieg gegen Jugurtha, den König von Numidien. Ihm zur Unterstützung kam Lucius Cornelius Sulla. Zusammen konnten sie Jugurtha gefangen nehmen und dadurch den Krieg im Jahr 106v.Chr. zugunsten der Römer entscheiden. Die Tatsache, dass seine Gegner Sulla diesen Sieg zuschrieben, war eine der Ursachen für die spätere erbitterte Feindschaft zwischen den beiden Führern.
Die von Marius eingeleiteten Heeresreformen, mit denen er die Umwandlung von einem Milizheer in ein Söldnerheer vollzog, bildeten die Voraussetzung für dessen spätere Erfolge. Zwei Jahre benötigte Marius für die endgültige Unterwerfung Numidiens. Dann rückte er 104v.Chr. als Konsul in Richtung Norden gegen die einfallenden germanischen Stämme der Kimbern und Teutonen vor. Infolge der drohenden Gefahr durch die Germanen wurde er mehrmals hintereinander zum Konsul gewählt, obgleich er nicht der Nobilität angehörte. Er bezwang die Teutonen im Jahr 102v.Chr. bei Aquae Sextiae (heute Aix-en-Provence) und ein Jahr später die Kimbern bei Vercellae (heute Vercelli im Piemont). Aufgrund all diese bedeutenden Erfolge wurde er als Retter des Staates im Jahr 100v.Chr. zum sechsten Mal zum Konsul gewählt.
Als man Sulla in seinem Konsulatsjahr 88v.Chr. den Oberbefehl im Krieg gegen den mächtigen König Mithridates VI. von Pontos übertrug, versuchte Marius, ihm das Kommando zu entziehen. Es kam zum Bürgerkrieg zwischen den Anhängern der beiden Führer, in dessen Verlauf Marius von Sulla geächtet wurde und aus Italien fliehen musste. Sulla begab sich daraufhin nach Kleinasien, um seinen Dienst anzutreten. Mit Unterstützung des Lucius Cornelius Cinna, eines erbitterten Gegners der Optimaten, kehrte Marius nach Italien zurück und nahm blutige Rache an seinen Gegnern.
Zum siebten Mal wurde er 86 v. Chr. zusammen mit Cinna zum Konsul gewählt. Wenige Tage vor seinem Amtsantritt verstarb Marius.
