Война Рима с царем Нумидии Югуртой (111–105 гг. до н. э.) показала степень разложения римской армии, особенно ее командного состава. Трудная победа Мария над нумидийцами позволила этому малообразованному, но храброму воину приступить к реорганизации римской армии. Реформы Гракха так и не смогли укрепить ее боеспособность. Разорение мелких землевладельцев привело к тому, что в армию уже некого было набирать. В связи с этим Марий стал принимать в легионы пролетаризованных, т. е. лишенных имущественного ценза, римских граждан. Государство брало на себя заботу о новом войске. Для легионера устанавливался шестнадцатилетний срок службы, после чего ему полагалось получить небольшой земельный надел.

Реформа армии имела огромные социальные последствия. Люмпен-пролетарии хлынули в легионы, так как военные походы сулили значительную добычу. Новую по составу армию Марий реорганизовал и установил в ней жесткую дисциплину. Ее боеспособность резко возросла. На смену крестьянскому ополчению пришли профессиональные воины, стремившиеся к грабежу и добыче, а по выслуге лет – к спокойной и обеспеченной жизни.

Значительны были и политические последствия реформы армии. События показали, что обычно избираемые консулы не всегда обладали способностью к полководческой деятельности. Поэтому, вопреки республиканской традиции, Мария избирали консулом много раз подряд. А это по сути превращало его в несменяемого диктатора. События последних десятилетий показали, что старое ополчение не способно успешно вести значительные военные операции и уже не может в полной мере обеспечить оборону государства. Именно поэтому только профессионализация армии смогла дать выход из сложившейся ситуации. Однако при этом нарушалась ранее незыблемая связь между понятием гражданин и воин, характерная для полисного устройства Рима. Теперь уже отнюдь не каждый гражданин становился на защиту республики, что являлось явным симптомом кризиса римской гражданской общины.

В 103 г. до н. э. один из видных популяров, Луций Апулей Сатурнин, став народным трибуном, попытался провести закон, согласно которому ветераны Мария должны были в обязательном порядке получить землю. Сенат этому решительно воспротивился. Однако в 100 г. до н. э., когда Марий в шестой раз был избран консулом, народным трибуном вновь стал Апулей Сатурнин. Он внес в сенат свой законопроект, по которому участки для ветеранов по 100 югеров предполагалось отвести в некоторых римских провинциях. Оказалось, однако, что этот закон не был выгоден ни оптиматам, ни популярам. Первые считали, что его реализация может значительно усилить влияние Мария. Вторым закон не позволял продолжить практику сбора налогов с земель, отходивших теперь ветеранам. Даже люмпен-пролетариат воспротивился закону: его кормили дешевым хлебом именно за счет доходов, получаемых с провинциальных земель.

И все же под давлением ветеранов Мария закон был принят. Однако на следующий год, когда в ходе предвыборной борьбы был убит кандидат в консулы из оптиматов, сенат объявил отечество в опасности. Подавить смуту было поручено Марию, который двинул войска против своих же недавних сторонников. Сам Сатурнин был убит. Дело в том, что состав популяров оказался крайне неоднородным: Марий поддерживал всадников, которые не были заинтересованы в переделе провинциальных земель; сельский же и городской плебс к этому времени был уже враждебен всадническому сословию и стал мишенью для нападок со стороны как всадников, так и сенаторов.