Назначенный квестором к Марию в его первое консульство, Сулла вместе с ним отправился в Африку, на войну с нумидийским царем Югуртой. До того как командование в этой войне перешло в руки Мария, военные действия шли крайне неудачно, а иногда даже и позорно для Римского государства: Югурте не раз удавалось подкупать римских военачальников. Предшественник Мария — аристократ и опытный полководец Квинт Цецилий Метелл, — хоть и оказался неподкупным, тем не менее тоже не сумел довести борьбу до победного конца. В успешном ходе войны под руководством Мария немалую роль сыграл его квестор Сулла. Он оказался храбрым офицером и ловким дипломатом. Например, Сулле удалось завоевать доверие царя Бокха, приходившегося Югурте тестем. Это обстоятельство имело решающее значение.
Когда Югурта, гонимый военными неудачами, вынужден был искать прибежища у своего тестя, Бокх вызвал к себе Суллу, пообещав ему выдать заклятого врага римлян. Сулла смело пошел на риск, который состоял в том, что Бокх, заполучив в свои руки и Югурту, и Суллу, мог не только не выполнить своего обещания, но и поступить диаметрально противоположным образом. И действительно, Бокх довольно долго колебался, взвешивал все «за» и «против», но, наконец, поступил по–своему «честно»: из двух предательств предпочел то, которое было задумано раньше и которое, видимо, сулило ему более спокойное и «гарантированное» будущее, т.е. решил выдать римлянам Югурту.
Еще в древности считалось, что именно с этого момента возникли неприязненные отношения между Марием и Суллой, ибо Марий ни с кем не хотел делиться своим триумфом. Неприязненные отношения перешли в открытую вражду, когда в ходе Союзнической войны молодой и удачливый полководец Сулла затмил своими успехами не только былую военную славу Мария, победившего Югурту, но и — что гораздо существеннее — недавнюю славу победителя кимвров и тевтонов. Плутарх говорит о том, что эта вражда, «столь незначительная и по–детски мелочная в своих истоках», привела в дальнейшем «к тирании и полному расстройству дел в государстве».
На консульских выборах 89 г. Сулла и вместе с ним Квинт Помпей (фигура малозаметная) были избраны консулами. Обстановка в Риме — как внутренняя, так и внешняя — была чрезвычайно сложной. Во–первых, еще не кончилась Союзническая война. Однако эта война уже не считалась главной опасностью: после ряда крупных поражений и гибели наиболее талантливых руководителей дело италиков в принципе было проиграно. Если же говорить об опасностях внешних, то гораздо более серьезную угрозу для римского могущества представляли в то время враждебные действия Митридата, царя Понта.
