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