Однако и Марию не удалось одержать быструю победу. Только в 105 г. Югурта был оттеснен во владения своего тестя, царя Мавритании Бокха. После долгих колебаний Бокх выдал его римлянам. Последний акт войны нанес удар по самолюбию Мария, поскольку честь поимки Югурты стали приписывать квестору Луцию Корнелию Сулле, которому Бокх непосредственно передал нумидийского царя. Сулла сближается с врагами Мария, возглавляемыми родом Метеллов.
И все же авторитет Мария был огромен. В январе 104 г. до н. э. ему устроили триумф (Торжественное шествие полководца и войска при их возвращении в Рим после победы), в котором провели пленного Югурту. После этого царь был задушен в римской тюрьме. Часть Нумидии стала римской провинцией.
Еще в 113 г. до н. э. на северо-востоке Италии появились два германских племени — кимвры и тевтоны. После серии поражений римлян постигла катастрофа. В 105 г. при Араузионе большая римская армия была наголову разбита германцами. Италия оказалась под угрозой вторжения. В этой ситуации происходит новое выдвижение Мария, который стал фактическим диктатором Рима. В течение пяти лет подряд он избирался консулом. В 102 г. в битве при Аквах Секстиевых Марий разбил тевтонов, а на следующий год при Верцеллах были уничтожены кимвры. Остатки этих племен были проданы в рабство.
С окончанием войны отпала необходимость в особых полномочиях Мария. Стремясь сохранить свою власть, он вступает в союз с двумя популярами — Сатурнином и Главцией. В 100 г. до н. э. Марий в шестой раз стал консулом, Сатурнин был избран народным трибуном, а Главция — претором.
Сатурнин предложил аграрный закон, который предполагал наделение землей ветеранов Мария, среди которых было немало италиков. Становясь жителями колоний, они автоматически приобретали права римского гражданства. Местом колонизации были выбраны Африка и Цизальпинская Галлия. Во главе всего предприятия Сатурнин планировал поставить Мария, в руках которого снова сосредоточивалась огромная власть. Закон имел еще один пункт: в случае принятия его народным собранием сенаторы под угрозой изгнания должны были принести присягу в том, что будут его соблюдать.
Значительная часть сената и плебса выступила против законопроекта. Лишь путем открытого насилия Сатурнин сумел его провести. Сенату пришлось дать требуемую присягу, только старый враг Мария Метелл отказался повиноваться закону и был вынужден покинуть Италию.
Год кончился, и наступили выборы на следующий, 99 г. Сатурнин снова прошел в трибуны, а Главция претендовал на консульство. Атмосфера накалилась, популяры использовали все средства, вплоть до политических убийств, что вызвало волну возмущения. Сенат объявил осадное положение в городе. Марий, опасаясь слишком дискредитировать себя союзом с Сатурнином, выступил на стороне сената. 10 декабря 100 г. до н. э. на форуме произошла схватка между людьми Сатурнина и сторонниками сенатской партии. Последние победили, а Сатурнин и Главция были убиты. Метелл вернулся из изгнания, Марий же надолго отошел от политики.