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