Когда нумидийский царь умер, он завещал государство двум своим сыновьям и своему племяннику Югурте. Подобный раздел власти между тремя правителями очень хорошо показал себя после смерти Масиниссы вероятно потому, что римляне поддерживали такое состояние. Однако Югурта не хотел ни с кем делить власть. После того как он убил одного из братьев, второй, Адгербал, бежал в Рим. Сенат, не зная положения дел, решил, что Нумидию необходимо разделить пополам между двумя оставшимися претендентами. Югурта отказался от такого раздела и осадил Адгербала в его столице. Римские торговцы, проживающие у осажденного царя, предложили ему сдаться при условии, что Югурта сохранит ему жизнь.
Югурта принял условия, но как только его двоюродный брат оказался у него в руках, он казнил его, а вместе с ним и многих римских торговцев. Это стало роковой ошибкой. Рим никогда не прощал убийство своих граждан. Югурте объявили войну, и сенат отправил в Африку римскую армию. Однако Югурта вскоре согласился сдаться римскому военачальнику при условии, что он останется на своем троне.
Такой ход событий сильно удивил римлян. Многие считали, что Югурта подкупил всех римских офицеров, с которыми он вел переговоры. Сенат создал комиссию по расследованию. Югурту привезли в Рим, и под гарантии безопасности ему велели назвать имена всех тех, кого он подкупил. Однако перед этим он как всегда подкупил трибуна, чтобы тот любым способом воспрепятствовал оглашению имен. Его также обвинили в убийстве его двоюродного брата, который жил в Риме по приглашению одного из консулов и потребовал передать ему трон Нумидии. К этому моменту стало очевидно, что с Югуртой было невозможно вести никакие дела. Его отправили обратно в Африку, и война возобновилась.
Плохо подготовленная римская армия потерпела от нумидийцев поражение и вынуждена была пройти под хомутом копий, как в прошлые неудачные времена самнитских войн. Римлян обязали покинуть Нумидию. В конце концов, в 109 году сенат понял, что Югурта — серьезный противник, и для продолжения войны в Африку отправили умелого и неподкупного военачальника.
Звали его Квинт Цецилий Метелл. Метелл был выходцем из семьи крупного сенатора. Среди клиентов Метелла числился и Гай Марий, который стал его легатом или представителем. К своим сорока восьми годам Марий сделал достойную для «нового человека» карьеру политика: в 114 году его выбрали претором и назначили наместником Лузитании. Он упорно стремился получить высшую государственную должность, даже если для этого пришлось бы пойти против своего давнего покровителя.
Метелл успешно вел военные действия, однако он действовал очень медленно. Югурта не сдавался. Марий начал волноваться, что война слишком затянулась. Он завоевал уважение среди рядовых римских воинов и римских торговцев, а также чувствовал поддержку избирателей на родине. Марий попросил у Метелла разрешение вернуться в Рим, чтобы выставить свою кандидатуру на должность консула и принять командование. Будучи аристократом, как и Марий, раздраженный Метелл не смог отказать, но отпустил язвительную шутку в адрес своего легата: «Так, значит, ты, милейший, собираешься покинуть нас и плыть домой домогаться консульства? — спросил он. — А не хочешь ли стать консулом в один год вот с этим моим сыном?» Сыну Метелла тогда было всего двадцать лет.
В результате Марию разрешили взять отпуск. В Риме он заручился поддержкой народа и всадников и добился избрания на должность консула. Народное собрание отклонило решение сената, который постановил продлить командование Метелла и не назначать на его место Мария. Такая узурпация традиционной роли сената в назначении военачальников в провинции создала опасный прецедент. Она подготовила почву для разных честолюбивых военачальников и политиков, которые старались обойти установленные законом ограничения.
Марий был полон решимости при первой же возможности покончить с Югуртой, для чего он произвел новый набор войск. Однако затем Марий обнаружил, что военные действия идут медленно и трудно, как и у его предшественника. Он захватывал крепость за крепостью, но легионы готовились к худшему — к битве с очень мобильным неприятелем на территории, которая хорошо подходит для развертывания конницы. Югурта укрепил свое положение, заключив союз со своим соседом, мавретанским царем Бокхом. В конце концов произошло генеральное сражение, в котором Марий одержал решительную победу. Она стала возможна в значительной степени благодаря Сулле. В наиболее ответственный момент он появился вместе со своей конницей.