Митридат, естественно, с этим не согласился и вторгся в Вифинию. При этом известии восстало население Азии, и армия Митридата вошла и туда, где ее ждала восторженная встреча. Такой оборот дел чрезвычайно встревожил римлян. На Восток были отправлены только что закончившие свой срок консулы 74 г. до н. э. Марк Аврелий Котта и Люций Лициний Лукулл. Лукуллу было поручено командовать в Азии и Киликии, а Когте — в Вифинии и охранять черноморские проливы. Котта не сумел справиться со своей задачей и бежал в город Халкедон, так что вся Вифиния перешла в руки Митридата, а находившиеся там римляне тоже бежали в Халкедон под защиту римского оружия. Но надежда на эту защиту оказалась тщетной, ибо когда Митридат подошел к Халкедону, Котта бежал и оттуда. Митридат осадил Халкедон, а затем и взял его, уничтожив или захватив в плен при этом огромную римскую эскадру в сотню боевых кораблей. После этих поражений армия Котты практически выбыла из войны, и вся тяжесть ее ведения пала на Лукулла.
Лукулл перед отправлением в Азию набрал легион воинов, а на месте принял командование над стоявшим там войском. Оно состояло в основном из бывших воинов Фимбрии, которые в свое время перешли к Сулле, но тот, боясь взять их с собой в Италию, оставил на Востоке. Бывшие фимбрианцы были воинами храбрыми, но за это время распустившимися и недисциплинированными, так что Лукуллу пришлось сначала восстанавливать порядок в армии, а уже потом приступать к активным военным действиям. В это время основные силы Митридата осаждали город Кизик, и Лукулл добился не только снятия осады, но и отступления понтийских войск, а затем в ходе преследования нанес им поражение у реки Граник, где когда-то свой первый бой против персов выиграл Александр Македонский. В то же время союзники римлян га-латы, жившие в центре Малой Азии, заставили Митридата очистить ряд малоазийских областей.
В следующих кампаниях Лукулл развивал свой успех. Римляне вторглись непосредственно в Понт, коренную область царства Митридата. Сам Митридат укрепился в городе Кабире на склонах гор. Но вскоре, не выдержав напряжения, понтийский царь стал отступать и оттуда. Воспользовавшись этим, Лукулл напал на него и полностью его разгромил. Митридат бежал в Армению к своему зятю Тиграну, а его сокровища и даже часть семьи попали в руки римлян. Узнав о бегстве Митридата, Лукулл сначала захватил Малую Армению, подчинил некоторые соседние племена, а затем потребовал от Тиграна выдачи его тестя. С этим требованием к Тиграну он отправил своего родственника Аппия Клавдия Пульхра. В это время армянский царь подчинял себе некоторые непокорные финикийские города, и Клавдий был вынужден дожидаться его в сирийской столице Антиохии. Он использовал вынужденное пребывание в этом городе для различных интриг, сумев настроить против Тиграна ряд эллинистических городов и мелких царств. Миссия Клавдия, как и ожидалось, закончилась безрезультатно, и тогда Лукулл от имени Римской республики объявил Тиграну войну.
Новая война вызвала недовольство солдат. Лукулл не очень-то позволял им грабить города Понта, а теперь еще вел их в дикие горы Армении, где, казалось, нечем поживиться. Решение полководца объявить эту войну вызвало недовольство и в Риме. В это время там рушились сулланские порядки, и действия такого активного оптимата, как Лукулл, вызывали все большее недовольство. Но Лукулл решительно продолжал военные действия. В 69 г. до н. э. он переправился через Евфрат и двинулся к армянской столице Тигранокерте, недавно основанной Тиграном. После поражения своего отряда, направленного против римлян, Тигран решил покинуть Тигранокерту и, отступив в горы Тавра, стал собирать армию для борьбы с римлянами. Но эта армия была разбита легатом Лукулла Люцием Лицинием Муреной, и Тигран бежал. После этого Лукулл осадил Тигранокерту. Собрав новое войско, армянский царь поспешил на выручку своей столице, но под стенами города снова потерпел поражение. Затем Лукулл штурмом взял Тигранокерту и разрушил ее. После таких огромных успехов Лукулл намеревался даже начать войну с парфянами, но подготовка Тиграном и Митридатом новой армии заставила его отказаться от этого намерения. Да и воины Лукулла все активнее выражали свое недовольство новым приказом.
Летом 68 г. до н. э. Лукулл снова выступил против Митридата и Тиграна. Их основные силы были сосредоточены в старой столице Армении Арташате. На берегу Аракса произошла новая битва, в которой римляне опять же одержали победу. Но идти дальше воины решительно отказались, и Лукуллу пришлось отступить. Он ушел на юг, а Митридат, воспользовавшись этим обстоятельством, собрал новую армию и вторгся в Понт. Оставленный охранять Понт Марк Фабий Адриан пытался остановить Митридата на армяно-понтийской границе, но был разбит. Потерпели поражение и римские союзники. В 67 г. до н. э. Митридат полностью восстановил свою власть в Понте.