Гай Марий, постепенно входивший в силу, и сам был клиентом Метеллов из числа эквитов. После десяти лет службы он выставил свою кандидатуру на должность военного трибуна – штатного офицера легионов, избираемого солдатами. По всей вероятности, положенный ему на этом посту год он провел на Балеарских островах, помогая одному из старших отпрысков рода Метеллов добиться первого в истории их поколения триумфа. Затем воспользовался пребыванием в этой должности, чтобы провести успешную кампанию по избранию на первую действительно важную магистратуру, и в 122 г. до н. э. стал квестором. На этом посту он, скорее всего, продолжил службу в легионах, которые на тот момент вели наступление на юге Галлии. И там впервые увидел те самые реки и холмы, где двадцать лет спустя ему предстояло одержать одну из самых эффектных побед за всю римскую историю.
Приступив к экспансии за пределами Италии, Рим двинулся по трем направлениям: на запад в Испанию, на юг в Африку и на восток к бассейну Эгейского моря. Но его северная граница не переживала никаких изменений, частью из-за Альп, высившихся вдали огромной естественной преградой. Но после великих завоеваний середины II в. до н. э., республике понадобилось наладить пути сообщения, чтобы снабжать свои обширные территории в Испании и Македонии. Как результат, легионы переправились через Альпы и втянулись в череду конфликтов с племенами, которые властвовали по ту сторону новых границ.
Впрочем, под римскую юрисдикцию полоса побережья между Альпами и Пиренеями перешла только в 120-х гг. до н. э. До этого защита региона возлагалась на город Массилия. Эта греко-финикийская колония, основанная в 600-х гг. до н. э., была другом и торговым партнером Рима с самых первых дней существования республики. В 125 г. до н. э. на Массилию напали салии – галльское племя, господствовавшее на равнинах между Альпами и рекой Рона, – и она обратилась за помощью к Риму. Радуясь возможности помочь другу (и еще больше радуясь поводу избавиться от консула Флакка, находившегося в Риме, пока он не продавил свой законопроект о предоставлении италикам гражданства), сенат отдал легионам приказ выступать на север. После нескольких лет сражений, заканчивавшихся с переменным успехом, римляне, наконец, заняли полоску земли шириной примерно двадцать миль от Массилии в глубь континента, и учредили там постоянную военную колонию под названием Аквы Секстиевы (ныне французский Экс-ан-Прованс). С момента своего основания в 122 г. до н. э. Аквы Секстиевы стали основной базой римских операций в Галлии.
Получив от римлян отпор, предводитель салиев собрал остатки своего племени и укрылся у аллоброгов – еще одного могущественного народа, контролировавшего территорию в верховьях Роны. Считая, что аллоброги представляют для Рима угрозу, в 122 г. до н. э. сенат отправил на охрану границ консула. В конце того же года легионы одолели аллоброгов в крупнейшей битве в окрестностях нынешнего Авиньона, а несколько месяцев спустя добились еще большего триумфа, одержав победу, к которой, по всей вероятности, был причастен Гай Марий. Кульминация этих первых Галльских войн наступила в конце лета 121 г. до н. э. В восьмидесяти километрах к северу от Акв Секстиевых римляне схлестнулись с коалицией галлов на берегах реки Изер.
Подробности того сражении до нас не дошли, но если учесть, что потери галлов составили около 120 000 человек, битва была поистине колоссальной. Только отсутствие детальных свидетельств помешало сражению на реке Изер стать одним из самых знаменитых во всей римской истории. После него Рим установил свою военную власть во всей Южной Галлии.
Когда римляне добились там господства, одна из сенатских фракций, объединившись с эквитами-торговцами, приложила немало усилий для учреждения в регионе постоянной гражданской колонии, с целью обеспечить пути снабжения на случай непредвиденных ситуаций в будущем. Сенат из кожи вон лез, чтобы отвергнуть это предложение, но когда ему оставалось совсем чуть-чуть, чтобы его окончательно парализовать, юный, блистательный оратор Луций Красс произнес в Народном собрании еще одну впечатляющую речь. Он решительно выступил в поддержку основания новой колонии и перетянул на свою сторону весь комиций – а вместе с ним и большинство коллег из сената. Когда в 118 г. до н. э. основали, наконец, Нарбо (ныне Нарбонн), вся Южная Галлия стала называться Нарбоннской. Создав в регионе постоянные поселения, римляне построили знаменитую Виа Домиция, т. е. Домициеву дорогу, которая связывала Италию с Испанией и действовала на постоянной основе. Ее можно увидеть и сегодня, двигаясь по южному побережью Франции.
Повоевав в 130-х гг. до н. э. в Испании и в 120-х гг. до н. э. в Галлии, Гай Марий отказался от военной карьеры в пользу гражданской, в 119 г. до н. э. выставил свою кандидатуру на выборах трибуна и, благодаря покровительству Метеллов, одержал победу. Но вместо того, чтобы в течение отведенного ему годичного срока завоевать новых союзников и друзей, Марий за это время практически всех от себя отвратил.