Мятежные легионы Суллы захватили Рим. Марий успел бежать в Африку. Сульпиций был убит, а его голова по приказу Суллы была выставлена на форуме. Захват Митридатом греческих территорий Рима требовал немедленного отъезда Суллы. Однако он не мог оставить Рим, не укрепив своих позиций. Сулла отменил законы, принятые Сульпицием, вводил в сенат 300 своих сторонников, провел новую конституцию. Теперь каждый проект закона перед внесением его в народное собрание должен был получить одобрение сената. Этим уничтожалась законодательная инициатива народных трибунов. Вводилась новая избирательная система. Сулла провел выборы консулов на 87 г. Ими стали Гней Октавий и Корнелий Цинна. Последний был из числа противников Суллы, но он уже ничего не успевал сделать. Сулла понимал, что сейчас для него важнее успешная война, которая позволит сохранить власть в Риме.
Война с Митридатом длилась два года и принесла Сулле славу великого полководца. У него была всего лишь 30-тысячная армия, не было денег, не было флота. За спиной, в Риме шла гражданская война, где сторонники Суллы терпели поражение. Его отстранили от должности главнокомандующего восточной армией после марианского переворота, а он продолжал отвоевывать у Митридата один город за другим. Победой закончилась осада Афин. Сулла разрушил Пирей – важнейший порт Митридата в Эгейском море. В битве при Херонее он разбил наголову Архелая, лучшего полководца Митридата. Как сообщал Плутарх, в битве при Орхомене, когда римская пехота, атакованная вражеской конницей, начала было отступать, Сулла, схватив знамя, увлек за собой воинов, крича: «Я здесь умру прекрасной смертью, римляне! А вы, когда вас спросят, где вы предали своего императора, не забудьте сказать: “Под Орхоменом”».
В 85 г. Митридат начал переговоры. Сулла вынужден был согласиться на заключение мира, так как Рим раздирала гражданская война. По условиям мирного договора Митридат возвращал римлянам все завоеванные территории в Малой Азии, выплачивал 3 тыс. талантов контрибуции и выдавал 80 боевых судов. Мир был подписан в августе 85 г. в городе Дардане на Геллеспонте. Плутарх в «Избранных жизнеописаниях» дает римскому полководцу такую оценку: «…Сулла был изгнанником, был побежден врагами. И в то самое время, как преследовали его жену, сравнивали с землею его дом, убивали его друзей, он, сражаясь ради отечества, воздвиг трофей, не сделал никакой уступки, не оказал никакого снисхождения Митридату; хотя тот предлагал ему союз и предоставлял войско для похода на врагов. Ничего более прекрасного, ничего более высокого по духу, чем эти подвиги, Сулла, кажется, вообще не совершил».
После заключения мира Сулла послал донесение в сенат и предупредил о своем возвращении. Однако вернулся он не сразу. Сначала он восстановил в отвоеванных римских владениях прежние порядки. Были отменены популистские законы Митридата, восстановлены налоги. Все недоимки, накопившиеся за годы войны, должны были быть выплачены. Провинция Азия облагалась военной контрибуцией в размере 20 тыс. талантов. Сторонники Митридата были казнены, города, оставшиеся верными Риму, щедро награждены. 84 г. Сулла провел в Греции, готовясь к войне в Италии. Весной 83 г. он с 40-тысячной армией, верной ему и благодарной за богатую добычу, высадился в Брундизии.
Начинался новый этап гражданской войны. Сулла знал, что за время его отсутствия власть в Риме захватили его противники Марий и Цинна, знал, что во время резни в июне 87 г. погибли его соратники Гней Октавиан, Люций Цезарь, Катулл и другие. Он знал, что сам объявлен вне закона, а его конституция отменена.
После смерти Мария в 86 г. Цинна три года фактически единолично возглавлял государство, был диктатором. Римляне не очень приветствовали его режим и были настроены на примирение с Суллой, особенно после того как он в послании сенату пообещал соблюдать права, предоставленные новым гражданам. Однако Цинна начал вооружать экспедицию против Суллы. Солдаты взбунтовались из-за того, что их отправляют в поход зимой, и в городе Анконе убили Цинну. Демократы потеряли своего вождя, единственного, пожалуй, кто мог оказать серьезное сопротивление Сулле.
По сравнению с войском консулов армия Суллы была немногочисленна, но это была армия-победительница, прошедшая войну, верившая в своего императора. Сулла имел в своем распоряжении огромные денежные средства. И самое главное – это был уже не тот Сулла: победа над Митридатом сделала его не только популярным, но и уверенным в своих силах, дерзким и жестоким к врагам. В Рим пришел не удачливый полководец, а беспощадный тиран.