По истечении срока своей городской претуры Марий получил в управление Дальнюю Испанию, одну из самых беспокойных римских провинций, где старую ненависть к римлянам не мог сдержать даже тот страх, который они внушали. Там шла настоящая война. Марий, возглавив провинцию, показал себя решительным и умелым полководцем. В течение короткого времени он заставил непокорные племена сложить оружие. Это была первая война, которую он выиграл под своими ауспициями38 и которая в полной мере выявила его решительный характер, его привычку доводить до конца начатое дело, не останавливаясь перед крайними средствами.

Репутация его в Риме была безупречной. Но отношение к нему знати оставалось по-прежнему холодным и высокомерным. Женитьба арпинца на патрицианке из рода Юлиев39 ничего не изменила. Между тем наступила пора неожиданных перемен, связанных со злополучной для знати Нумидийской войной. После принятия закона Мамилия40 о попустительстве Югурте многие оптиматы, изобличенные во взятках, полученных от нумидийского царя, с великим позором осуждены были на изгнание. Сокрушительные поражения римлян в войне с кимврами давали повод для обвинений всего знатного сословия в неспособности управлять делами государства. Впервые после Гракхов подняла голову партия популяров41, которая быстро набирала силу, используя малейший промах своих политических противников.

В консульство Марка Юния Силана42 и Квинта Цецилия Метелла43 Марий отправился вместе с последним в качестве его легата44 против Югурты. Метелл взял его себе в помощники, учитывая храбрость, боевой опыт и популярность, какой пользовался арпинец в солдатской массе.

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

В один прекрасный день он явился к Метеллу и, объявив о своем намерении, просил проконсула45 дать ему отпуск для поездки в Рим.

Метелл очень холодно отнесся к затее своего легата. Одна только мысль, что этот простолюдин может появиться на Марсовом поле в тоге соискателя консульской должности, казалась ему кощунственной. Убежденный оптимат, он готов был грудью защищать привилегии своего благородного сословия. Он считал их священными.

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