A nagy létszámú, új haderő jól vizsgázott, bár csak a második, Kr. e. 106 elején indított hadjáratban sikerült eltántorítani Mauretania királyát, Bocchust sógora, Jugurtha támogatásától. Mindebben nagy szerepet játszott a tehetséges ifjú arisztokrata quaestor, Lucius Cornelius Sulla, a későbbi dictator diplomáciai érzéke. Plutarkhosz szerint Marius már ekkor féltékeny volt rá. A hadvezér még két évet Numidiában töltött, hogy pacifikálja az országot és új alapokra helyezze a római hatalmat a területen.

Közben új veszedelem jelentkezett, ezúttal jóval közelebb Itáliához: kimberek, teutonok és más barbárok százezres tömegei gyülekeztek az Alpok északi oldalán, és betörésük csak idő kérdése volt.

Kr. e. 113-tól kezdve Illyricum, később Gallia Narbonensis, végül Gallia Cisalpina területén jelentek meg, és számos nagy vereséget mértek a római haderőre. Kr. e. 107-ben Marius consultársa, Lucius Cassius Longinus is odaveszett a harcban. A rettegő rómaiak egyetlen megoldást láttak a dologra: Mariust távollétében ismét consullá választották, alig három évvel az első magistratura lejárta után, tehát teljességgel szabályellenesen. Mindenesetre a veszélyben a pártharcok ideiglenesen szüneteltek, Marius pedig Kr. e. 104. január 1-jén triumphusszal kezdte meg újabb consuli évét Rómában.