尚不清楚马略在阿埃米利亚努斯到达时是否已经在努曼提亚服役。

在努曼提亚的军队中服役期间，他的军事才能引起了西庇阿·阿埃米利亚努斯的注意。

根据普鲁塔克的说法，在一次晚餐后的谈话中，当谈话转向将军时，有人问西庇阿·阿埃米利亚努斯，罗马人民将在哪里找到他合适的继任者，年轻的西庇阿轻轻拍了拍马略的肩膀，说：“也许就是这个人。”

看来，即使在他军事生涯的早期阶段，马略也有在罗马从事政治生涯的雄心。

尽管选民们并不认识他，但他还是根据自己的成就当选为二十四位特别军事保民官之一。

选举后，他很可能为昆图斯·凯基利乌斯·梅泰卢斯·巴利阿里库斯（Quintus Caecilius Metellus Balearicus）服务，帮助他赢得了胜利。

接下来，马略在阿尔皮努姆地方公职选举失败后，竞选财政大臣。

他竞选地方职务以获得家乡的支持，但输给了地方竞争者。

然而，也可能马略根本没有竞选财务官，而是直接跳到了平民法官（plebeian tribune）一职。

他参加了公元前121年伊泽尔河战役（Battle of the Isère River）并为罗马获得重大胜利，这场胜利永久性地巩固了罗马对南高卢的控制。

公元前120年，马略被重新选为平民法官，赢得了梅泰利家族（Metelli）的支持，特别是卢修斯·卡西利乌斯·梅特鲁斯·德尔马提库斯（Lucius Caecilius Metellus Dalmaticus）。

可是，盖乌斯·马略却违背了梅泰利家族的意愿，推动了一项法律，限制富人在选举中的干预。

在公元前130年代，投票的方式在选择官员、通过法律和决定法律案件的选举中引入了无记名投票，取代了之前的口头投票制度。

富人们仍然试图通过检查选票来影响投票，而盖乌斯·马略通过法律限制选民投票时通过的通道，以防止外人骚扰选民或看到投票结果。

盖乌斯·马略随后因否决扩展粮食救济的法案而使平民疏远。

不久之后，在公元前117年，盖乌斯·马略竞选市政官并落选。

显然，到了这个时候，由于任何未来的执政官都必须承担巨大的财务压力，马略已经积累了或得到了相当可观的财务资源。

这次失败可能部分是由于梅泰利家族的敌意。

在公元前116年，他勉强赢得了次年执政官的选举，排名垫底，但立即被指控为贿选（ambitus）。

在共和国中期和后期，被指控选举腐败是很常见的，审判的细节模糊不清或者是杜撰的。

然而，马略在被项指控后无罪释放，并在罗马平静地度过了一年的执法官生涯，职务可能是外事法官或贪污法庭的法官。

公元前 114 年，马略被派往备受追捧的西班牙省份（Hispania Ulterior）担任总督，在那里他进行了一些小规模的军事行动，以清除未开发矿区的强盗。

他在行省内治理了两年，然后在公元前113年晚些时候，回到罗马，个人财富大幅增加。

他回国时未获得凯旋，但他娶了尤利亚（Julia），尤利乌斯·凯撒（Julius Caesar）的姑姑。

尤利乌斯·凯撒家族是一个贵族家族，但在这一时期还难以从执法官晋升为执政官。

在公元前2世纪，这个家族曾成功获得执政官职位一次，时间是在公元前157年。

这个婚姻对双方都有利：马略通过嫁入贵族家庭获得了声望，而尤利乌斯家族则获得了大量的活力和财富。