Действуя в соответствии с указаниями Метелла, Бомилькар стал советовать царю подумать о разорённой стране и сдаться на милость победителя. Югурта вновь послал к Метеллу послов, предлагая сдать ему царство и сдаться самому в обмен на обещание сохранить жизнь себе и своим сыновьям. Но Метелл опять, как и раньше, такого обещания не дал, а стал выставлять предварительные требования. От Югурты потребовали двести тысяч фунтов серебра, всех слонов, определённое количество лошадей и оружия. Кроме того, Метелл потребовал выдать всех перебежчиков, а они были лучшими солдатами Югурты, солдатами, лучше всех других обученных римской тактике и владению оружием, а кроме того, наиболее верными солдатами, так как ни бежать, ни предать они не могли — в Риме их ждала лишь смерть. Поколебавшись, Югурта удовлетворил все требования римлян. Метелл получил и слонов, и деньги, и оружие. Привели к римскому полководцу и закованных в цепи перебежчиков, лишь некоторые из них успели сбежать в соседнюю Мавретанию.
Когда царь лишился своей ударной мощи и денег, ему было велено прибыть самому в город Тисидий, но по-прежнему никто нс дал ему никаких гарантий безопасности. После долгих раздумий и колебаний царь решил вновь продолжить войну, но вести войну ему теперь стало ещё тяжелее.
Спеша выслужиться перед Метеллом и считая, что царь достаточно ослаблен, Бомилькар подготовил переворот, однако тут предателю не повезло — одно из его писем было перехвачено и доставлено царю, после чего и Бомилькар, и все его сообщники были казнены. Но хотя Югурта ещё имел сторонников и иногда добивался определённых тактических успехов в борьбе с римлянами, войну он явно проигрывал.
Единственной надеждой Югурты на спасение оставалось лишь вступление на его стороне в войну с римлянами Мавретании, царь которой Бокх Первый был женат на его дочери. В этом случае война могла затянуться, и Югурта имел основания надеяться на заключение мира на приемлемых условиях. Бокх отнюдь не желал воевать с Римом. Более того, с началом Югуртинской войны он даже прислал в Рим послов с просьбой о союзе и дружбе, но, как пишет Саллюстий Крисп, «этому делу, сулившему нам огромные преимущества в начатой войне, помешали несколько человек, ослеплённых алчностью, для которых привычно было продавать всё подряд — и честное, и бесчестное» [Sallustius «В. Jugurt», 80, 5]. Были ли римские магистраты, сорвавшие переговоры с Мавретанией, подкуплены Югуртой или просто потребовали от посланников Бокха взяток, которые те им не дали, неизвестно. Но Югурта сумел этим воспользоваться и убедить обиженного римлянами Бокха совместно выступить против Рима.
Узнав о союзе Югурты и Бокха, Метелл отступил к Цирте и, не спеша начинать сражение с их объединёнными войсками, начал переговоры с Бок-хом, убеждая его не становиться врагом и теперь уж сам от имени Рима предлагая Бокху союз. Бокх отвечал, что согласен, но просил дать возможность заключить мир и Югурте, а Метелл возражал. Долгие месяцы они обменивались гонцами, время шло, а боевые действия не начинались, что устраивало и царей, и Метелла, который не спешил воевать ещё и потому, что к этому времени истекли его консульские полномочия, а римский сенат поручил продолжение войны в Нумидии избранному одним из консулов на 107 г. до н. э. Гаю Марию, ранее бывшему одним из легатов Метелла. Почитав себя обойдённым, Метелл вовсе не собирался искать опасностей, облегчая триумф своему преемнику, а потому предпочитал тянуть время под благовидным предлогом.
Шёл уже пятый год Югуртинской войны. Отдельных полководцев и сенаторов затяжная война вполне устраивала, однако большинство римлян негодовало, не понимая, почему римская армия никак не может расправиться с каким-то нумидийским царём. Воспользовавшись этим, ставший консулом Гай Марий набрал себе для продолжения войны огромное количество новобранцев, причём впервые «не по обычаю предков, и не по разрядам, а всякого, кто пожелает, большей частью лично внесённых в списки» [Sallustius «В. Jugurt», 86, 2]. Формальной причиной этого был недостаток граждан соответствующих цензов, реальной же причиной была политика. Будучи сам выходцем из низов, Гай Марий был крайне заинтересован в том, чтобы в армии служило как можно больше простолюдинов, «ибо именно эти люди его прославили и возвысили, а для человека, стремящегося к господству, наиболее подходящие люди — самые нуждающиеся, которые не дорожат имуществом, поскольку у них ничего нет, и всё, что им приносит доход, кажется честным» [Sallustius «В. Jugurt», 86, 3]. Для разгрома Югурты хватило бы и гораздо меньших сил, но Гай Марий умело использовал ситуацию для укрепления своего личного влияния, «отправившись в Африку с подкреплением, намного более многочисленным, чем было определено» [Sallustius «В. Jugurt», 86, 4].
Сменив Квинта Цецилия Метелла на посту главнокомандующего и имея теперь гораздо больше войск, чем его предшественник, Гай Марий активизировал войну Югурта потерял ещё несколько крепостей, а помощь от Бокха всё не приходила. «Узнав, что тот медлит и, колеблясь, взвешивает доводы в пользу войны и мира, Югурта снова, по обыкновению, подкупил подарками его приближённых, а самому мавру обещал третью часть Нумидии, если римляне будут выдворены из Африки или если война будет закончена без ущерба для его царства» [Sallustius «В. Jugurt», 97, 2]. Соблазнившись такой наградой, Бокх наконец выступил.
Под конец 107 г. до н. э., когда войска Гая Мария, разорявшие Нумидию, уже отходили на зимовку в римскую Африку, Бокх и Югурта внезапно атаковали их, выбрав время под вечер. Войско царей было более многочисленным и им поначалу удалось добиться некоторого успеха, с наступлением темноты римляне отступили с равнины на холмы, где легче было обороняться. Но оттеснив римлян к холмам, мавретанцы и нумидийцы, посчитав себя победителями, проявили беспечность и расположились в беспорядке, не подумав об укреплении своего лагеря. Всю ночь они ликовали, а радость оказалась преждевременной: под утро, выждав когда «варвары» уснут, Гай Марий перешёл в наступление и разгромил утратившего бдительность противника. Через четыре дня Югурта и Бокх, собрав отступившие в беспорядке войска, вновь дали Гаю Марию бой неподалёку от Цирты, столицы Нумидии. К этому времени на помощь царям подошёл сын Бокха, царевич Воллукс, с большим отрядом пехоты, и новое сражение было для римлян ещё более напряжённым, чем первое, однако в конце концов римская выучка и лучшее вооружение привели к тому, что объединённые войска царей вновь были разбиты.
И тут римляне вновь перешли от военных действий к дипломатии: несмотря на то, что Югурта и Бокх были разбиты, Гай Марий убедился в том, что война сразу с двумя царями будет долгой и опасной, а потому начал переговоры с Бокхом, обещая мир, если тот разорвёт союз с Югуртой. Бокх после двух неудачных сражений поначалу решил было согласиться, но Югурта, узнав об этом, сумел опять подкупить ближайших советников мавретанского царя, и Бокх заколебался. Боясь и дальнейшей войны с римлянами, и перспективы разорвать союз с Югуртой до того, как заключит приемлемый мир с римлянами, Бокх послал несколько своих наиболее верных придворных, чтобы те наверняка договорились с римлянами о мире и получили гарантии мира не только от полководцев, но и от сената.
Посольство отправлялось в тайне от Югурты, но, видимо, это не осталось для него тайной: по дороге послы, следовавшие в силу секретности своей миссии с небольшой охраной, были ограблены якобы разбойниками, а скорее всего, действовавшими под видом разбойников людьми Югурты. К римскому квестору Луцию Корнелию Сулле, помощнику Гая Мария, послы прибыли без подарков и «лишённые знаков своего достоинства» [Sallustius «В. Jugurt», 103, 2]. Но Сулла повёл себя мудро и вместо того чтобы разгневаться, принял посланцев Бокха благожелательно. Более того, прикинув, что дружба с Бокхом может сослужить неплохую службу и ему лично, Сулла научил послов, что и как им следует говорить Гаю Марию, чтобы получить разрешение отправиться в Рим, и что следует говорить римским сенаторам, чтобы те соизволили заключить мир. В Риме послы были приняты благосклонно, и им было заявлено, что сенат и римский народ готовы простить Бокха, раз он раскаивается, но союза и дружбы он будет удостоен, когда заслужит их. Таким образом, Бокху дали выйти из войны, но ясно намекнули, что на твёрдый мир он может рассчитывать, лишь предав Югурту.
