Разгром гракханцев означал поражение римской демократии. Но вернуться к прежнему положению было невозможно. Продолжал действовать аграрный закон, действенность которого, однако, через несколько лет была подорвана приравнением участков, полученных по этому закону, к частной собственности, что открывало путь к их скупке крупными землевладельцами. Как и предлагал в свое время Гай Гракх, римское правительство стало выводить колонии в провинции. А главное, суд так и остался в руках всадников. В результате они практически вошли в правящий слой государства. Но это его не усилило, ибо две группы — сенаторы и всадники — охраняли свои интересы, во многом противоречащие друг другу. Не только не исчезло, но еще более усилилось соперничество внутри знати. Временно объединившись для борьбы с общим врагом, отдельные олигархические группировки снова и даже с еще большей силой принялись бороться между собой. Следствием всего этого стал новый этап кризиса Римской республики.
В 112 г. до н. э. началась война Рима с нумидийским царем Югуртой. Римляне долго не могли справиться с ним, и в народе росла уверенность, что это происходит из-за бездарности и коррумпированности сенаторских полководцев. И консулом на 107 г. до н. э. со специальным поручением вести войну с Югуртой был избран «новый человек» Гай Марий. В целом успех в войне был на стороне римлян, но добиться решающей победы не смог и Марий. Тем не менее римляне регулярно продлевали ему командование, и, наконец, в 105 г. до н. э. мавританский царь Бокх, во владения которого бежал Югурта, выдал того римлянам, на чем война и завершилась. В январе 104 г. до н. э. Марий, заочно избранный консулом на этот год, справил триумф. Победа над Югуртой вызвала энтузиазм народной массы. Война, проигрываемая аристократическими полководцами не столько из-за слабости войска, сколько из-за алчности подкупаемых полководцев, была блестяще выиграна человеком, ставшим консулом и поководцем только благодаря своим заслугам, а не знатному происхождению. После этой победы Марий надолго стал любимцем римлян.
Приблизительно в то же время римлянам пришлось впервые столкнуться с германскими племенами. Это были кимвры и тевтоны, которые перешли Рейн и затем вторглись в римскую провинцию Трансальпийскую Галлию. Римская армия, возглавляемая обоими консулами Квинтом Сервилием Цепионом и Гнеем Маллием Максимом, была наголову разгромлена около города Араузиона. И это страшно напугало римлян. Консулом заочно (что в то время случалось очень редко) был избран Марий, еще воевавший в то время в Африке. Понимая все трудности борьбы, Марий начал прежде всего тренировать свою армию, изматывая ее бесконечными походами и физическим трудом. Солдаты роптали, но Марий был непреклонен. А доверие народа к нему было столь велико, что, несмотря на длительное, казалось бы, бездействие, его дважды избирали консулом — на 103 и 102 гг. до н. э. А в 102 г. до н. э. в ожесточенном сражении около города Аквы Секстин армия Мария наголову разгромила тевтонов, уничтожив практически все это племя. Но в это же время кимвры, обойдя Альпы, с северо-востока вторглись в Цизальпинскую Галлию, откуда открывался прямой путь в Италию и на Рим. Коллега Мария Квинт Лутаций Катулл был разбит, но сумел добиться заключения годичного перемирия. Марий с торжеством вернулся в Рим, но от триумфа отказался до тех пор, пока оставались непобежденные враги. Он добился своего избрания на 101 г. до н. э., а затем направился в Цизальпинскую Галлию, где армией продолжал командовать Катулл в ранге проконсула. И в 101 г. до н. э. Марий и Катулл полностью разбили кимвров. Страшная опасность, нависшая над Италией, была устранена. Марий и Катулл справили великолепный триумф, а авторитет Мария в Риме стал неоспоримым.
Во время войн в Африке и Галлии Марий провел ряд мероприятий, которые привели к коренным изменениям в римской армии. Они касались разных сторон воинской жизни, но главным стал новый принцип формирования войска. До сих пор римская армия формировалась преимущественно из средних слоев населения, главным образом крестьян. И резкое сокращение этих слоев ставило перед римскими политиками неразрешимые задачи. Марий решил пойти по другому пути. Он не стал набирать войско в соответствии с имущественным цензом, как это было принято, а начал вербовать добровольцев. И это были в основном люди, стоявшие вне ценза, т. е. бедняки, которые ранее к военной службе не привлекались. Не имея никаких или почти никаких средств существования, эти люди получали в армии возможность сравнительно благополучной жизни, разумеется, под вечным страхом гибели в бою. И это создавало совершенно новые отношения между воинами и полководцем. Последний выступал в какой-то степени как патрон своих солдат, а те — как его клиенты.