Далекий путь от лагеря до Утики у моря Марий совершил за два с половиной дня. Когда он перед тем, как сесть на корабль, принес жертву, то прорицатель, говорят, объявил ему, что боги сулили ему великое счастье, выше всяких надежд. Полный радостных надежд, он прибыл на корабле в Рим на четвертый день. Народ приветствовал его с восторгом и решил возвести в консульское звание вновь прибывшего, вышедшего из среды народной и блеском своим затмевавшего мужей знати. Хотя и неприятен был этот прямой и грубый воин, этот выскочка без родословной гордым аристократам, они не отваживались, однако, чинить ему существенных затруднений на пути к достижению цели. Когда Марий в день выбора был приведен трибуном Манилием Манцином в народное собрание и стал добиваться консульского звания, то он обещал закончить тягостную войну за короткое время и передать в руки римлян Югурту, мертвого или живого. При этом он не упустил случая набросить на Метелла тень подозрения и обвинить его в преднамеренном продлении войны. Народ отнесся к выбору плебея как к делу партии и значительным большинством голосов передал ему консульство на 107 г. и главнокомандование в Югуртинской войне. С этого времени Марий становится главой демократической партии и выступает повсюду горячим противником аристократии, которая до сих пор мешала его успехам на политическом поприще.

Собираясь на войну, Марий составил новые отряды, и притом, в противовес существовавшему до того обычаю, из низших классов народа. Этим он, разумеется, приобрел для своих дальнейших планов верных приверженцев, но вместе с тем ухудшил дух войска, так как неимущие люди стали отныне смотреть на военную службу как на ремесло и источник заработка и сражались не столько ради отечества, сколько ради своего полководца. Когда Марий явился в Африку, то оскорбленный Метелл уклонился от свидания с ним; еще до прибытия своего преемника он выехал из лагеря и передал ему войско через посредничество легата Рутилия Руфа. Метелл поставил Югурту в весьма затруднительное положение. Марий продолжал войну с успехом, одержал над неприятелем несколько побед и вынудил его, наконец, бежать к своему тестю Бокху, царю мавританскому. Бокх колебался: выдать ли зятя своего римлянам или взяться, в защиту его, за оружие. Но благодаря дипломатической ловкости квестора Луция Суллы удалось принудить Бокха к выдаче Югурты. Побежденный царь был доставлен в лагерь Мария, закованным в цепи (106 г. до P. X.).

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

1 января 104 г. был великий триумф Мария, причем выставлены были напоказ 3007 фунтов золота, 5775 фунтов серебра в слитках и 287 тыс. драхм чеканенной монетой. Но самым интересным предметом триумфального шествия был закованный в цепи царь, который так долго шутил недобрые шутки над величием римского государства. Несчастье и позор повергли его в состояние помешательства. Когда по окончании торжества его привели в темницу, сняли с него силой исподнее платье, а некоторые сорвали с него золотые ушные кольца, вместе с ушной мочкой, и когда его затем обнаженного спустили в глубокую яму, он, оскалив зубы и засмеявшись, воскликнул: «О, Геркулес, как холодна ваша ванна!» После шестидневных мучений он умер от голода.