Армию, вверенную его командованию в Африке, Метелл застал в безобразнейшем состоянии. Римский историк Саллюстий, посвятивший Югуртинской войне одно из своих сочинений, пишет, что это было
Действия Метелла и его неподкупность произвели на Югурту такое впечатление, что он, еще ни разу не вступив в сражение, отправил консулу послов с выражением полной покорности и просил лишь сохранить жизнь ему и его сыновьям. Однако после пережитых унижений римляне могли удовлетвориться только полным подчинением Нумидии и казнью дерзкого царя. Югурте ничего не оставалось делать, как снова взяться за оружие. На равнине у реки Мутул он занял выгодные позиции, устроил засады и поджидал римское войско, продвигавшееся в глубь Нумидии. Но все замыслы Югурты разбились о доблесть и стойкость римской пехоты. Нумидийцы были отброшены и обращены в бегство. После этого Югурта перешел, по сути дела, к партизанской войне, поддерживая те города, которые оказывали сопротивление римлянам. Метелл пытался захватить Югурту, действуя против него его же излюбленными средствами – подкупом и хитростью. Но эти попытки не дали результата. Избегая открытых сражений, дерзкий враг появлялся то в одном, то в другом месте и оставался неуловимым. Туземные племена продолжали ему помогать, считая его освободителем от римского гнета. К тому же мавританский царь Бокх, на дочери которого был женат Югурта, объединился со своим зятем и привел ему на помощь свою многочисленную конницу. Война грозила затянуться. В Риме, где не ослабевало народное недовольство знатью, Метелла стали открыто обвинять в недостаточно активных действиях. Эти нападки тем более усиливались, что все солдаты писали из Африки домой, что не будет ни конца, ни предела войне с нумидийцами до тех пор, пока консулом не изберут Гая Мария.
За два года войны Марий приобрел в войсках огромную популярность. Среди командиров он выделялся своим благоразумием, предусмотрительностью и смелостью. Для рядовых легионеров Марий был своим не только по происхождению. Они видели в нем настоящего соратника и боевого товарища. Он не уступал простым воинам выдержкой и выносливостью в ратных трудах, нередко вместе со всеми копал ров или ставил частокол вокруг лагеря. Для противников правящей сенатской олигархии Марий был наиболее подходящим кандидатом на предстоящих консульских выборах. Честолюбивый крестьянин из Арпина и сам давно втайне мечтал о высшей должности. Теперь же, приобретя широкую известность, он решил выставить свою кандидатуру, тем более что от одного гадателя он получил благоприятное предсказание. Метелл имел все основания видеть в Марии политического противника аристократии и поэтому чинил ему всяческие препятствия и отпустил его в Рим всего лишь за 20 дней до голосования.
Прибыв в столицу в самый последний момент, Марий, обиженный на Метелла, обрушился с резкими нападками и на него, и на всю бездарную знать. Сам же он обещал народу в кратчайший срок закончить злополучную войну. Смелые речи Мария привлекли к нему плебеев и всадников. Он был избран консулом 107 г. до н. э. при всеобщем ликовании народа и получил назначение командующим в Нумидию – напрямую от народного собрания, хотя раньше сенат, пользуясь своим законным правом, продлил полномочия Метелла. Марий имел все основания сказать, что консулат достался ему как военная добыча после победы над враждебной знатью.