По истечении срока наместничества Марий возвращается в Рим и получает от Метелла предложение сопровождать его на войну с Югуртой. Его отношения с Метеллом имеют, по-видимому, давнюю предысторию. У Плутарха есть неясное упоминание о том, что еще отец Мария служил дому Метеллов. Возможно, что Квинт Метелл помог молодому Гаю вступить в испанское войско римлян, несмотря на отсутствие у него минимально необходимого достатка. С другой стороны, тот же Плутарх пишет о столкновении Мария, уже в качестве народного трибуна, с Метеллом, которому он даже будто бы грозил арестом. Тем не менее Метелл берет Мария с собой в Нумидию и, ценя его военные заслуги, поручает ответственное командование в бою. Но вместе с тем дистанция между знатным аристократом и крестьянским сыном остается неизменной. И потому Метелл был неприятно удивлен, узнав от Мария о его непомерно честолюбивом желании баллотироваться на очередных выборах консулов. К тому же это было вызовом и нарушением традиции. Хотя после того как плебеи добились полного уравнения в правах с патрициями, любой гражданин Рима мог быть избран консулом, до сих пор на высший государственный пост осмеливались претендовать только аристократы. Любые другие магистратуры были уже доступны простому народу, но, как свидетельствует историк Саллюстий:
«...консульскую должность знать пока сохраняла за собой, еще передавая ее из рук в руки. Всякого нового человека, как бы он ни прославился, какие бы подвиги ни совершил, считали недостойным этой чести и как бы оскверняющим ее». (Саллюстий. Югуртинская война. 63, 2)
Римские историки утверждают, что дерзкое решение Мария было подкреплено предсказанием великого и чудесного будущего, будто бы сделанного неким гаруспиком. Реакцию Метелла на претензии его легата и последствия этой реакции живо описывает тот же Саллюстий:
«Марий, — пишет он, — увидя, что слова гаруспика совпадают с тем, к чему его влекут тайные желания, просит у Метелла отпуск, чтобы выступить соискателем на выборах. Хотя Метелл и был щедро наделен доблестью, жаждой славы и другими качествами, желанными для честных людей, он все же отличался презрительным высокомерием — общим пороком знати. Озадаченный необычной просьбой, он сперва удивился намерению Мария и как бы по дружбе стал предостерегать его от столь неразумной затеи и от стремления, не соответствующего его положению... Не переубедив его, Метелл обещал удовлетворить его просьбу, как только позволят обстоятельства. И впоследствии, когда Марий неоднократно обращался к нему с этой же просьбой, Метелл, говорят, советовал ему не спешить с отъездом: для него, дескать, будет не поздно добиваться консулата вместе с его сыном. А тот в это время под началом отца там же проходил военную службу, и было ему лет двадцать». (Там же. 63, 3)
Естественно, что Марий, которому уже сорок семь и немало боевых заслуг за плечами, был оскорблен таким предложением.
«Этот ответ, — продолжает Саллюстий, — разжег в Марии решимость добиться магистратуры, к какой он стремился, и раздражение против Метелла. И он стал слушаться двух наихудших советчиков — честолюбия и гнева, и не останавливался ни перед поступком, ни перед словом, лишь бы они способствовали его избранию: от солдат, которыми он командовал на зимних квартирах, он уже не требовал прежней строгой дисциплины; в присутствии торговцев, весьма многочисленных в Утике, он вел несдержанные и одновременно хвастливые речи о войне — дескать, если бы ему доверили половину войска, то Югурта уже через несколько дней оказался бы в его руках, закованным в цепи. Командующий, по его словам, нарочно затягивает войну, так как он, человек тщеславный и по-царски высокомерный, чересчур упоен своей властью. Все это казалось людям тем более убедительным, что продолжительная война их разоряла, а для человека, охваченного каким-либо желанием, все делается недостаточно быстро...» (Там же. 63, 4)
Агитация Мария, как он и рассчитывал, доходит до простого народа в Риме. По свидетельству Плутарха:
«...все писали из лагеря домой, что не будет ни конца, ни предела войне, пока Гая Мария не изберут консулом». (Плутарх. Сравнительные жизнеописания. Гай Марий. VII)
Марий и сам пишет в столицу своим друзьям, всадникам и торговцам, а также находящемуся в Риме еще одному внуку Массиниссы, Гауду побуждая их осуждать на форуме Метелла и требовать передачи командования ему Марию. Момент благоприятен еще тем, что недавно закончился суд над бывшими главнокомандующими римского войска, показавший их продажность и измену. Во время этого суда вскрылись и факты подкупа Югуртой римских сенаторов, а потому сенат не осмелится помешать народу избрать Гая Мария консулом.