Marius, som tillhörde en riddarsläkt från Arpinum i östra Latium, tjänade under Scipio Aemilianus i Spanien 134–133 f.Kr., tjänstgjorde som folktribun 119, praetor 115 och ståthållare i Spanien 114. Omkring 110 f.Kr. äktade han Julia, medlem av den patriciska gens Iulia. Han följde 109 konsuln Metellus i kriget mot