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