Bár a senatus korábban megszavazta Metellusnak a hadjárat folytatásának jogát, a nép Marius kezébe adta Numidiát. Ő és a néppárt hatalmas győzelemként élte meg a consullá választását, amit folyvást hangoztatott is. A megalázott arisztokrácia egyre jobban gyűlölte a homo novust, aki szintén nem felejtette el a korábbi sérelmeket. Mindazonáltal első dolga volt az afrikai hadműveletek befejezése.

Ennek érdekében olyasmit tett, ami alapvetően meghatározta a Római Birodalom későbbi történetét. A sorozás korábbi, vagyoni helyzettől függő classisokon és centuriákon alapuló sorozási rendszerét felrúgva bárkit hajlandó volt zsoldosként alkalmazni.
Ezzel a vagyontalanok számára is lehetőség nyílt a gyors, bár veszélyes vagyonszerzésre, és a kisbirtokosoknak sem kellett elhagyniuk földjeiket, ha nem akarták. Ez mind a római állam, mind a közrendűek számára számos előnyt rejtett, bár hamarosan a zsoldhoz és zsákmányhoz lojális haderő hátulütői is jelentkeztek.