По возвращении из Азии Сулла пришел в столкновение с Марием, которому возраставшая слава молодого соперника стала казаться все более опасной. Царь Бокх посвятил Капитолию группу статуй, изображавших выдачу Югурты Сулле, и это обстоятельство задело Мария в такой степени, что он старался удалить статуи из храма. Ссора обоих соперников теперь грозила возмутить город; но союзническая война остановила на время дальнейший разрыв.
Установив на скорую руку мир, Сулла поспешил со своими легионами на восток, где успехи Митридата настоятельно требовали его присутствия.
Митридат VI Евпатор, или Дионисий, именуемый также Великим, был в то время опаснейшим врагом римлян. Он понимал, что независимость его государства не может сохраниться из-за постоянно возраставшего владычества римлян в Азии, что либо он должен пасть, либо Рим «с его волчьей натурой, ненасытной жаждой крови, земель и золота», и решил биться до победы. Унаследовав государство Понтийское, береговую страну в Каппадокии у Черного моря, он расширил его во все стороны, приобрел Колхиду и основал в северной части Черного моря, в Крыму и прилежащих местностях, так называемое Босфорское царство, которое доставляло ему ежегодно 200 талантов и 180 тыс. четвериков хлеба. На востоке он присоединил к своим владениям Малую Армению и заключил с царем Армении Тиграном, за которого выдал дочь свою Клеопатру, дружественный союз, прикрывавший его с тыла в его предприятиях против запада. В Малой Азии он захватила Каппадокию и Пафлагонию.
Митридат понял, что римляне стремятся погубить его, и стал готовиться всеми силами к войне. Его обширные земли доставляли ему корабли, людей и деньги в изобилии. Во главе его войска стояли отличные полководцы, как, например, братья Неоптолем и Архелай. Немногочисленные римские отряды, размещенные в разных местах Азии, были разбиты. Азиаты и эллины повсюду с восторгом принимали победоносного царя, который провозглашал себя поборником и освободителем эллинской национальности. Они посылали к нему, как к «спасительному богу», своих вестников и приглашали его прибыть в города их; они захватывали римских офицеров и отправляли их связанными к царю. Вскоре царь издал в Эфбее всем подчиненным ему наместникам и городам приказ: в один день перебить всех италийцев, свободных и несвободных, кого им удастся захватить, без различия пола и возраста, трупы их бросить на съедение птицам, имущество конфисковать и одну половину его отдать убийцам, а другую – отослать царю. Таким образом, в один день умерщвлено до 150 тыс. италийцев, мужчин, женщин и детей; азиаты с наслаждением и жестокостью избивали римлян, которые так долго притесняли их и разоряли их страну (88 г. до Р.Х.).
Митридат был теперь единственным властителем Малой Азии, и флот его господствовал на Восточном море. Он послал затем полководца своего Архелая с войском и флотом в Грецию, чтобы сразиться там с римлянами. Афенион, афинский философ низкого происхождения, которого афиняне послали к царю при известии о его победах, возвратился теперь в Афины во главе 2 тыс. понтийских воинов и без труда добился того, что граждане отошли от Рима и примкнули к царю. Афенион господствовал в городе, как тиран, преследовал богатых и знатных как приверженцев римских притеснителей и отбирал у них имущество.
В то время как эти события совершались на востоке, в Риме и Италии свирепствовала гражданская война и обессиливала тех, кто должен был наказать царя Митридата. Только весной 87 г. Сулла с пятью легионами, около 30 тыс. человек, высадился у берегов Эпира, без денег и без единого военного корабля. Его средства для такой значительной и занимавшей такое большое пространство войны были, следовательно, крайне невелики; но он не падал духом и быстро двинулся на неприятеля, полагаясь на свое счастье. В Беотии он разбил Архелая и Афениона и затем завладел почти без сопротивления всем греческим материком, за исключением Афин и Пирея. Отделив небольшие отряды для защиты остальной страны от нападений неприятельского войска, он с главными силами своими расположился лагерем при Элевзисе и Мегаре, чтобы отсюда командовать Пелопоннесом и осадить Афины и Пирей.