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