Положение ухудшилось в 110 г. до н. э., когда преемник консула Бестии Спурий Постумий Альбин предпринял вялую атаку на Югурту, а затем отвел свою плохо дисциплинированную армию на зимовку, поручив командование своему брату Авлу. Тем временем в Риме два народных трибуна, желая продлить свои полномочия, задержали выборы на все должности. Эти политические интриги привели к тому, что командование осталось в руках Авла Постумия Альбина куда дольше, чем предполагалось.

Решив выжать из своего назначения все, что возможно, Авл Постумий напал на город Сутул, в котором находилась главная казна Югурты. Нумидийский царь притворился, что готов снова — вести переговоры, и втайне начал подкупать центурионов и других офицеров в римской армии. Затем он предпринял неожиданное ночное нападение на Постумия. В лагере римлян возникла паника, когда часть легионеров, целая когорта лигурийской пехоты и две турмы (turmae) фракийской кавалерии совместно дезертировали, а старший центурион — примипил (primus pilus) III легиона позволил врагу пройти через ту часть укреплений, которую он должен был защищать. Слабое сопротивление армии быстро закончилось после того, как многие римляне убежали из лагеря к ближайшему холму, оставив нумидийцам на разграбление свои палатки.

На следующий день Югурта, окружив Авла и его солдат, предложил закончить войну договором. В ответ на признание Югурты законным царем Нумидии тот должен позволить римлянам спокойно уйти, как только они подвергнутся символическому унижению, пройдя под аркой из трех копий[24]. Точное происхождение это архаического ритуала неизвестно, он, очевидно, подразумевал потерю солдатами своего статуса воинов. Также точно не известно, был ли он широко распространен за пределами Италии или его проводили враги Рима, зная о том, насколько этот обряд унизителен для римлян. Как и в случае с Нуманцией, сенат незамедлительно отверг договор. Однако этот демарш сената не мог уменьшить возмущение народа, поскольку всем было ясно, что катастрофа вызвана некомпетентностью и коррупцией.

В 109 г. до н. э. командующим на войне с Югуртой стал консул Квинт Цецилий Метелл, младший брат Делматика. Он не стал набирать новую армию, а пополнил численность легионов, находившихся в Африке. Размолвка между Марием и Метеллами, очевидно, не была окончательной, ибо Марий и Публий Рутилий Руф сопровождали Квинта Металла в качестве его старших легатов. Поскольку с консулом теперь находились два легата, служивших в Нуманции, неудивительно, что для приведения легионов в форму стали применяться многие методы Сципиона Эмилиана.

Войска Альбина провели последние месяцы в праздном безделье, даже не утруждая себя укреплением лагеря должным образом. Местоположение лагеря менялось, лишь когда начинало не хватать фуража или же вонь от их собственных нечистот становилась нестерпимой. Солдаты и рабы из лагеря мародерствовали и грабили, как им заблагорассудится.

Метелл предпринял меры, очень похожие на те, что использовал Сципион Эмилиан. Торговцы и прочие ненужные нахлебники были изгнаны, а солдатам запретили покупать еду — многие продавали свою порцию зерна, чтобы приобрести готовый белый хлеб и не есть хлеб из непросеянной муки, который они должны были печь сами. Простым солдатам также запретили держать собственных рабов или иметь вьючных животных. Армия стала сниматься с лагеря каждый день и перемещаться на новую позицию, где разбивала походный лагерь, как если бы находилась на вражеской территории. Как и Сципион, Метелл и его легаты своими действиями подавали пример простым воинам во время марша. При этом они постоянно двигались вдоль колонны, следя за тем, чтобы как целые подразделения, так и отдельные солдаты занимают положенное им место и всегда должным образом экипированы и готовы к бою.

Когда Метелл счел свою армию достаточно подготовленной, он начал наступление на Югурту. Сначала царь избегал боя, поэтому римляне переключили свое внимание на его города, захватив несколько небольших крепостей и столицу — город Цирта. Такие потери нанесли серьезный урон престижу Югурты и побудили его напасть на римскую армию, когда она передвигалась по открытой местности у реки Мутул.

После беспорядочного скоротечного боя, во время которого подвижные вражеские войска заставили колонны римлян разделиться на несколько частей, нумидийцев наконец удалось оттеснить, нанеся им серьезный урон. Большинство их боевых слонов было убито или захвачено в плен. Римляне также потеряли немало убитыми и ранеными, и Метелл дал армии недолгий отдых, позволив солдатам восстановить силы и позаботиться о раненых. Он также провел построения, на которых наградил отличившихся в бою.

Спустя четыре дня римляне снова начали опустошать самые плодородные области Нумидии, угрожая ее городам и твердыням. Брать штурмом укрепленные города всегда было делом трудным, и Метелл был вынужден отвести свои войска от Замы после осады, во время которой произошли упорные и кровавые стычки. Самым удобным было избавиться от Югурты тем же способом, каким ликвидировали Вириата. Римляне подкупили нескольких царских командиров, чтобы те убили Югурту. Но заговор был раскрыт и провалился.

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

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

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

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