A vidéken nevelkedett Marius minden bizonnyal a régi római ideál megtestesítője volt, mivel vagyoni helyzete folytán nem is ismerkedhetett meg az ekkortájt arisztokrata berkekben népszerűvé váló görög kultúrával. A sors fintora, hogy mégsem ő vált a konzervatív optimaták kedvelt figurájává, hanem a philhellén Sulla.

Marius először katonaként futott be nagy karriert. Először Hispania területén szolgált, Kr. e. 134-ben jelen volt Numantia ostrománál, ahol bátorságával és vasfegyelmével számos kitüntetést és dicséretet kapott. A hadvezér Publius Cornelius Scipio Africanus állítólag az asztaltársaságába fogadta, és egy alkalommal a jövendő tehetséges hadvezéreként méltatta alárendeltjét. Ezt követően mintegy 15 évig nem hallunk róla, de kétségtelen, hogy továbbra is katonáskodott. A katonai tribunusi rangig vitte, és oly népszerű lett, hogy Kr. e. 119-ben akadály nélkül néptribunusszá választották.