Tribunátusa alatt Marius későbbi parancsnoka, Quintus Caecilius Metellus támogatását élvezte, illetve a Herenniusok továbbra is patronálták. Egyetlen törvényjavaslatát ismerjük, amikor is a szavazóhelyiségek átalakítását követelte, hogy megelőzhesse a tehetősek megfélemlítési törekvéseit.
A Caius Gracchusszal nemrég leszámoló, római politikát uraló optimaták a senatus elé idézték, de ő rendkívül határozottan állt ki az ügy mellett: nemhogy megfélemlítette volna az idézés, de még a két consul, Lucius Aurelius Cotta és Lucius Caecilius Metellus Dalmaticus - patrónusa fivére - letartóztatásával fenyegetőzött.
A megdöbbent testület végül elfogadta az indítványt, Marius respektusa pedig az égbe szökött a plebs körében. Igaz, hamarosan jelentősen vissza is esett, amikor tiltakozott az ingyengabonaosztás ellen, félve, hogy az csak elősegíti a plebs haszonleső lumpenproletariátussá válását.

A senatori arisztokrácia azonnal felismerte benne a potenciális vetélytársat, ezért sikeresen megcsáklyázták jelentkezését az aedilisi rangra, és majdnem elérték, hogy a praetorságról is lecsússzon, ráadásul még vesztegetéssel is megvádolták. Kr. e. 115-ös praetorsága alatt alkotott maradandót, nem így Kr. e. 114-es propraetori évében, amikor sikeresen megtisztította Hispania Ulteriort az azt elárasztó banditáktól és útonállóktól.