Для своего похода он, не обращая внимания на звания и происхождение, избрал себе в помощники испытанных и дельных офицеров, среди которых был и Гай Марий, который со времени возвращения своего из Испании, хотя и не выделялся ни знатностью рода, ни богатством, ни красноречием, пользовался, однако, в Риме большим почетом вследствие своей неутомимой деятельности и простого образа жизни. Почету этому придала новый блеск женитьба его на Юлии, из древнего знатного рода Цезарей, тетке великого диктатора Гая Юлия Цезаря.
В Югуртинскую войну Марий в качестве легата оказал самые существенные услуги. Он помог Метеллу восстановить упавшую дисциплину в войске и снова возвратил римским знаменам победу. Повсюду восхвалялись его храбрость и военное искусство, его хитрость, благоразумие и строгая жизнь; сердца солдат он расположил к себе тем, что не уклонялся ни от какой тяжелой работы и делил с ними все труды и опасности. Его имя и слава были у всех на устах, и солдаты писали домой, что нельзя думать об окончании войны, если Мария не изберут консулом и главнокомандующим. Метелл не мог по этому поводу скрыть свое неудовольствие, и, по-видимому, не обошлось без неприятных сцен между обоими гордыми мужами. Явная вражда началась между ними, когда Марий попросил у главнокомандующего отпуск в Рим, чтобы добиваться консульства. Так как Марий настаивал на своем увольнении, то он его наконец получил, когда до консульских выборов оставалось всего 12 дней.
Далекий путь от лагеря до Утики у моря Марий совершил за два с половиной дня. Когда он перед тем, как сесть на корабль, принес жертву, то прорицатель, говорят, объявил ему, что боги сулили ему великое счастье, выше всяких надежд. Полный радостных надежд, он прибыл на корабле в Рим на четвертый день. Народ приветствовал его с восторгом и решил возвести в консульское звание вновь прибывшего, вышедшего из среды народной и блеском своим затмевавшего мужей знати. Хотя и неприятен был этот прямой и грубый воин, этот выскочка без родословной гордым аристократам, они не отваживались, однако, чинить ему существенных затруднений на пути к достижению цели. Когда Марий в день выбора был приведен трибуном Манилием Манцином в народное собрание и стал добиваться консульского звания, то он обещал закончить тягостную войну за короткое время и передать в руки римлян Югурту, мертвого или живого. При этом он не упустил случая набросить на Метелла тень подозрения и обвинить его в преднамеренном продлении войны. Народ отнесся к выбору плебея как к делу партии и значительным большинством голосов передал ему консульство на 107 г. и главнокомандование в Югуртинской войне. С этого времени Марий становится главой демократической партии и выступает повсюду горячим противником аристократии, которая до сих пор мешала его успехам на политическом поприще.
Собираясь на войну, Марий составил новые отряды, и притом, в противовес существовавшему до того обычаю, из низших классов народа. Этим он, разумеется, приобрел для своих дальнейших планов верных приверженцев, но вместе с тем ухудшил дух войска, так как неимущие люди стали отныне смотреть на военную службу как на ремесло и источник заработка и сражались не столько ради отечества, сколько ради своего полководца. Когда Марий явился в Африку, то оскорбленный Метелл уклонился от свидания с ним; еще до прибытия своего преемника он выехал из лагеря и передал ему войско через посредничество легата Рутилия Руфа. Метелл поставил Югурту в весьма затруднительное положение. Марий продолжал войну с успехом, одержал над неприятелем несколько побед и вынудил его, наконец, бежать к своему тестю Бокху, царю мавританскому. Бокх колебался: выдать ли зятя своего римлянам или взяться, в защиту его, за оружие. Но благодаря дипломатической ловкости квестора Луция Суллы удалось принудить Бокха к выдаче Югурты. Побежденный царь был доставлен в лагерь Мария, закованным в цепи (106 г. до P. X.).
Этот успех Суллы был первым зародышем ревности и вражды, обнаружившихся впоследствии между Суллой и Марием. Аристократы из зависти и ненависти умаляли заслуги Мария, приписывая первые и важнейшие успехи Метеллу, а окончание войны – Сулле. Последний чересчур много кичился своим подвигом; он велел изготовить себе перстень, на котором был вырезан Югурта в том виде, в каком он был выдан ему Бокхом. Все это раздражало честолюбивого Мария, не терпевшего, чтобы кто-либо другой участвовал в его славе, и слишком ясно презревшего намерения аристократов.