Так как подвоз продовольствия в Рим был отрезан, население начало голодать. Цинна снова обратился к рабам, обещая им свободу. На сей раз большое число рабов перебежало к нему. Войско, которым располагал Октавий, тоже оказалось не совсем надежным. В этой ситуации сенат принял решение направить посольство к Цинне для переговоров. Однако послы вернулись ни с чем, так как они не знали, что им следует ответить на вопрос Цинны: явились ли они к нему как к консулу или как к частному лицу? Через некоторое время к Цинне было направлено новое посольство, которое обратилось к нему уже как к консулу и просило лишь об одном — чтобы он дал клятву не производить резни.

Переговоры происходили в присутствии Мария. Он стоял возле кресла Цинны и не произнес ни одного слова. Сам Цинна наотрез отказался принести клятву, но сказал, что по своей воле не будет виновен в убийстве хотя бы одного человека. Попутно он добавил, чтобы Октавий не попадался ему на глаза, а то с ним может что–нибудь произойти и помимо воли самого Цинны. Сенат принял все условия и предложил Цинне и Марию вступить в город. Но так как Марий с мрачной иронией заметил, что для изгнанников нет доступа в город, то народные трибуны немедленно аннулировали его изгнание (как и всех прочих, изгнанных в консульство Суллы).

Ближайшие события показали, что опасения сената были не напрасны. Как только войско Цинны и Мария вступило в город, началась страшная резня, сопровождаемая разграблением имущества сулланцев. Солдаты Мария убивали всех, на кого он указывал рукой, и даже тех, на чьи поклоны он не отвечал. Гней Октавий, который, несмотря на зловещее предупреждение Цинны, отказался покинуть город, был убит, и его голова — впервые в истории Рима голова римского консула — была выставлена на форуме перед ораторской трибуной. Цинна также весьма своеобразно отблагодарил тех рабов, которые, по его призыву, перебежали к нему, когда он ещё стоял лагерем у Стен Рима: как–то ночью, когда рабы спали, он окружил их отрядом, состоящим из галлов, и всех перебил. Аппиан, сообщающий об этом факте, с удовлетворением заключает: рабы получили должное возмездие за проявленное ими нарушение верности своим господам.

Резня продолжалась около недели. Затем наступило некоторое затишье, в городе устанавливался порядок. Вскоре прошли консульские выборы. Консулами на 86 г. оказались избраны Марий и Цинна. Для Мария это было седьмое — но и последнее — консульство. Буквально через несколько дней после своего избрания он умер.

Все законы Суллы были отменены. Новые граждане распределялись по 35 трибам. Проводилась частичная кассация долгов, приступили к организации колонии в Капуе, которую еще хотел вывести Гай Гракх. Наконец, было принято решение о том, чтобы лишить Суллу прав командующего и на войну с Митридатом направлялся Луций Валерий Флакк, избранный консулом (на освободившееся место Мария).

Как же развивались за это время события на восточном театре войны? Когда Сулла еще переправлялся со своим войском в Грецию, положение Митридата и его успехи превзошли всякое ожидание. Он владел Вифинией и Каппадокией, отнял провинцию Азию у римлян, один из его сыновей управлял основными владениями в Понте и на Боспоре, другой же сын — Ариарат — с большой армией покорял Фракию и Македонию. Полководец Митридата Архелай подчинил Кикладские острова, Эвбею и оперировал на территории Греции. Афинами управлял фактический ставленник царя — тиран Аристион.

Сулла, высадившись в 87 г. в Эпире, совершил оттуда переход в Беотию. Затем он приступил к осаде Афин. Велись подкопы, строились осадные машины, и так как строительного материала не хватало, Сулла не пощадил священные рощи Академии и Ликея: они были вырублены. Нуждаясь в деньгах, он посылал своих представителей в знаменитейшие храмы и святилища Эллады, с тем чтобы они доставляли ему оттуда накопленные сокровища. Когда один из его посланцев, не рискуя изъять сокровища Дельфийского храма, сообщил Сулле, что в храме сама собой зазвучала кифара и что это следует рассматривать как знак, поданный богами, Сулла насмешливо ответил этому уполномоченному, чтобы он действовал решительнее, ибо таким путем боги выражают отнюдь не гнев, но скорее радость и согласие. Когда делегаты, направленные к Сулле Аристионом, вместо деловых переговоров начали говорить о великом прошлом Афин, о Тесее и о Персидских войнах, то Сулла не менее насмешливо заметил им: «Идите–ка отсюда, милейшие, и все свои россказни прихватите с собой; римляне ведь послали меня в Афины не учиться, а усмирять изменников».

Наконец, когда город был взят и предан Суллой на поток и разграбление, когда кровь погибших, по словам очевидцев, обагрила не только городские области, но даже вытекла за ворота, когда и сам Сулла насытился местью, он произнес несколько слов в похвалу древним афинянам и сказал, что дарует «немногих многим, милуя живых ради мертвых».

Решительное сражение с полководцами Митридата произошло на территории Беотии у города Херонеи (86 г.). Битва была упорной и окончилась победой римлян. Следующую важную победу Сулла одержал при Орхомене, в результате чего остатки войск Митридата вынуждены были полностью очистить территорию Греции.

Эти две победы решили по существу исход войны. Положение Митридата резко ухудшилось. В 86 г. в Греции высадился со своим войском Валерий Флакк. Однако его солдаты начали перебегать к Сулле, и вскоре Флакк был убит. Командование перешло к его легату — Гаю Флавию Фимбрии. Ему удалось вытеснить Митридата из Пергама, и сюда же, в провинцию Азию, двинул свои войска Сулла. Митридату не оставалось ничего другого, как просить о мире. Его личная встреча с Суллой произошла в Дардане. Сулла держал себя весьма высокомерно и, не отвечая на приветствие понтийского царя, сразу поставил вопрос ребром: согласен ли Митридат на условия, переданные ему Суллой при предварительных переговорах? Когда царь отвечал на эти слова молчанием, Сулла заявил: просители должны говорить первыми, молчать могут победители. Митридат был вынужден пойти на условия, предложенные Суллой. Он очищал все захваченные им ранее территории, выплачивал контрибуцию в 3 тыс. талантов и выдавал римлянам часть своего флота.