Саллюстий дает ему такую характеристику: «Сулла принадлежал к знатному патрицианскому роду, к его ветви, уже почти угасшей ввиду бездеятельности предков. В знании греческой и латинской литературы он не уступал ученейшим людям, отличался огромной выдержкой, был жаден до наслаждений, но еще более до славы. На досуге он любил предаваться роскоши, но плотские радости все же никогда не отвлекали его отдел; правда, в семейной жизни он мог бы вести себя более достойно. Он был красноречив, хитер, легко вступал в дружеские связи, в делах умел необычайно тонко притворяться. Был щедр на многое, а более всего — на деньги. И хотя до победы в гражданской войне он был счастливейшим из всех, все-таки его удача никогда не была большей, чем его настойчивость, и многие спрашивали себя, более ли он храбр или более счастлив»
Тот факт, что Сулла оставался легатом, а затем военным трибуном Мария в Германской войне, показывает, что тогда их отношения еще сохранялись, однако в 102 году происходит его сближение с оптиматами, обратившими внимание на талантливого офицера. Сулла стал легатом Катула и участвовал в сражении при Верцеллах. Вероятно, успешные действия армии Катула в немалой степени были и его засугой.
В начале своей политической карьеры Сулла не планировал стать эдилом и был провален на преторских выборах 95 года. Только в 93 году он был избран, а в 92 году стал пропретором Киликии и сумел провести удачную дипломатическую акцию против Митридата, посадив на престол римского ставленника Армобарзана. В 90–89 годах Сулла стал легатом в южной армии римлян, действовавших против Самния.
После ранения командующего, консула Л. Юлия Цезаря, он стал фактиченски командующим этой армии и оставался им в течение 89 года. Именно Сулла разгромил самнитов, представлял-вших одну из главных сил повстанцев. Центры восстания Эзерния и Бовиан пали, остатки разбитых самнитов и луканов ушли в горы. К началу 88 года армия осадила последний оплот инсургентов, город Нолу.
В 90 году Рим вступил в конфликт с Митридатом, а в 88 году армии понтийского царя нанесли внезапный удар, захватили Малую Азию и Грецию. С помощью Митридата в Афинах произошел государственный переворот, и власть захватил тиран Аристион (88), стремившийся, опираясь на помощь Митридата, добиться былой независимости для Афин.
Рим начал терять свои восточные владения. Ведение войны было поручено прославившемуся в союзническую войну Луцию Корнелию Сулле, однако на политической арене появился Марий, заключивший союз с близким другом погибшего реформатора Друза — трибуном П Сульлицием Руфом. Марий и Сульпиций смогли опереться на те силы, которые поддержали Мария в 100 е годы, а также на партию Друза и большое количество всадников.
Как и ранее, Марий в основном преследовал личные цели — получение армии и командование в войне. Сульпиций рассчитывал на помощь марианцев в завершении реформ Друза. Первым предложением Сульпиция был закон о распределении италиков по всем 35 трибам, который он внес на рас смотрение народного собрания. В оппозиции Сульпицию оказался не только сенат, но и масса старых граждан в народном собрании. Консулы объявили юстиции, и в ответ на это Сульпиций организовал на них нападение. Во время схватки погиб сын второго консула Помпея Руфа, и Сулла под угрозой физической расправы отменил свое решение. После этого Сульпиций провел закон об италиках и решение о назначении Мария командующим в Митридатовой войне.
Традиционные методы борьбы были исчерпаны, однако Сулла перевел конфликт в новую стадию Он направился в Нолу, где стояла армия, которую он хотел вести против Митридата, и повернул ее против Рима. Город был взят войсками. Сулла созвал народное собрание, отменил законы Сульпиция, объявил Сульпиция, Мария и 10 лидеров их партии вне закона. Сульпиций был убит, а Марий бежал в Африку. Вероятно, в это время проводился закон Суллы, по которому любой законопроект, выдвинутый трибуном, нуждался в утверждении его сенатом.
Цель переворота Суллы заключалась в ликвидации законов Сульпиция, что и было сделано. Тем не менее значение этого переворота оказалось огромным. Впервые армия использовалась в борьбе за власть не как политическое орудие, а в своем прямом военном качестве. Конфликт перешел на новый уровень. Положение Суллы после переворота было довольно сложным. Несмотря на то что его армия контролировала ситуацию, оппозиция оставалась достаточно сильной. Партия Мария и Сульпиция не была разгромлена, к ней присоединились многие недовольные методами Суллы. Первые симптомы проявились в массовом протесте и требованиях вернуть изгнанников. Консул Помпеи Руф был послан принять армию Гнея Помпея Страбона, однако, когда он прибыл в армию, взбунтовавшиеся солдаты его убили. Наконец, на 87 году консулами были избраны оптимат Гней Октавий и противник Суллы Корнелий Цинна.