Praetori éve után Marius nem azonnal indult a consuli választásokon, bár minden bizonnyal célul tűzte ki, hogy elérje a köztársaság legmagasabb méltóságát. Ekkortájt építette ki kapcsolatait a Juliusokkal, amikor is elvette idősebb Caius Julius Caesar testvérét. Népszerűsége így is nőttön nőtt, pedig sem gazdag, sem jó szónok nem volt, ami pedig sok esetben elengedhetetlen volt a nép jóindulatának megnyeréséhez.
A római közvéleményt megundorította a numidiai Jugurtha ellen hosszú ideje hiába folyó, az arisztokrata hadvezérek tehetségtelenségét és megvesztegethetőségét bizonyító háború. Ennek vezetése Marius pártfogójára, Quintus Metellusra szállt, aki legatusként magával vitte a középkorú politikust is.

Kr. e. 109-ben mutatkozhatott meg a maga teljességében Marius hadvezéri zsenije. Sőt mi több, egyszerű életvitelével és a velük megosztott terhekkel a katonák szívében is igen jó pozíciókat szerzett, aminek Rómában is pozitív hatásai voltak. Marius vallásosságát (mindig magával vitte szír vagy zsidó jósnőjét, Marthát) is jó jelnek vélték közrendűek a mind világiasabb arisztokratákhoz képest.

Kr. e. 108-ban Marius többször kérte Metellust, hogy engedje haza a consulválasztásra. Az arisztokrataként erre már nem volt hajlandó, és különféle okokra hivatkozva nem engedte el. Marius végül intrikákba fogott, és elterjesztette, hogy a fővezért lefizették, ezért elhúzza a háborút - mi több, egymaga a hadsereg felével azonnali győzelmet tudna kivívni.
A hír Rómába is eljutott, Metellus pedig jobbnak látta elengedni korábban vérig sértett alárendeltjét (ugyanis azt találta mondani neki, hogy ráér a fiával együtt pályázni, aki pedig ekkor még csak huszonéves volt, tehát Mariusnak hatvanéves koráig kellett volna várnia a megválasztásra). A szűkre szabott kimenő ellenére jó széllel időben megérkezett a személyes jelenlétet igénylő választásra, és el is nyerte Kr. e. 107 consuli rangját.