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

В следующих кампаниях Лукулл развивал свой успех. Римляне вторглись непосредственно в Понт, коренную область царства Митридата. Сам Митридат укрепился в городе Кабире на склонах гор. Но вскоре, не выдержав напряжения, понтийский царь стал отступать и оттуда. Воспользовавшись этим, Лукулл напал на него и полностью его разгромил. Митридат бежал в Армению к своему зятю Тиграну, а его сокровища и даже часть семьи попали в руки римлян. Узнав о бегстве Митридата, Лукулл сначала захватил Малую Армению, подчинил некоторые соседние племена, а затем потребовал от Тиграна выдачи его тестя. С этим требованием к Тиграну он отправил своего родственника Аппия Клавдия Пульхра. В это время армянский царь подчинял себе некоторые непокорные финикийские города, и Клавдий был вынужден дожидаться его в сирийской столице Антиохии. Он использовал вынужденное пребывание в этом городе для различных интриг, сумев настроить против Тиграна ряд эллинистических городов и мелких царств. Миссия Клавдия, как и ожидалось, закончилась безрезультатно, и тогда Лукулл от имени Римской республики объявил Тиграну войну.

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

Летом 68 г. до н. э. Лукулл снова выступил против Митридата и Тиграна. Их основные силы были сосредоточены в старой столице Армении Арташате. На берегу Аракса произошла новая битва, в которой римляне опять же одержали победу. Но идти дальше воины решительно отказались, и Лукуллу пришлось отступить. Он ушел на юг, а Митридат, воспользовавшись этим обстоятельством, собрал новую армию и вторгся в Понт. Оставленный охранять Понт Марк Фабий Адриан пытался остановить Митридата на армяно-понтийской границе, но был разбит. Потерпели поражение и римские союзники. В 67 г. до н. э. Митридат полностью восстановил свою власть в Понте.

Управляя провинцией Азией, Лукулл проявил себя довольно умелым администратором. Одной из причин антиримского восстания в этой провинции была жадность римских ростовщиков, и Лукулл сумел ограничить ее предельной нормой ростовщического процента в 12 % годовых. Вообще-то это была самая высокая норма, признаваемая римскими законами, но в провинциях ростовщики с законами не считались, доводя процент до 48. Эти меры привлекли к проконсулу сердца многих провинциалов, но вызвали ярость ростовщиков. Еще страшнее для Лукулла оказалось растущее недовольство солдат. Сам Лукулл был одним из самых богатых людей Рима, а после войны его богатство еще более увеличилось. Но своим воинам он особенно обогащаться не давал. И в конце концов они отказались повиноваться полководцу.

В результате не только Митридат вернул себе Понт, но и Тигран, восстановив свою власть в Армении, стал разорять набегами соседнюю Каппадокию. Лукулл же был вынужден бессильно смотреть на усиление, казалось бы, разгромленного врага. В 66 г. до н. э. проконсулом Азии был направлен Маний Ацилий Глабрион, но он пассивно стоял в своей провинции, а Лукулл с остатками своей армии едва удерживал Киликию.

В этих условиях в том же 66 г. до н. э. народный трибун Гай Манилий внес предложение назначить верховным главнокомандующим для войны с Митридатом и Тиграном Помпея, к которому переходила бы верховная власть в восточных провинциях, включая Азию и недавно присоединенную Вифинию, флот и неограниченная власть на море; к нему должны были перейти также войска Лукулла и Глабриона, и он получал право объявления войны. Это предложение опять же вызвало резкое противодействие сената. Против него решительно выступили лидеры оптиматов Квинт Лутаций Катул, который недавно столь яростно и столь неудачно пытался противодействовать назначению Помпея воевать с пиратами, и знаменитый оратор того времени Квинт Гортензий. Последний заявлял, что, конечно, если нужно избрать одного мужа для войны с Митридатом, то это, разумеется, Помпей, но как раз для блага республики и свободы и нельзя предоставлять всю полноту власти одному человеку. Зато энергичным сторонником Манилия и Помпея стал другой известный оратор — набиравший в то время силу и известность Марк Туллий Цицерон, занимавший в тот год пост претора. Горячая речь Цицерона, доказывавшего, что только Помпей способен одолеть такого страшного врага, как Митридат, перевесила чашу весов, да и победы Помпея говорили сами за себя. Предложение Манилия было принято и стало законом. По этому закону Помпей получал еще большие полномочия, чем Лукулл и чем он сам совсем недавно в войне с пиратами. По существу, он становился совершенно бесконтрольным владыкой всего Восточного Средиземноморья.

Не возвращаясь в Рим, Помпей принял новое поручение. Он прибыл в Киликию и начал переговоры с Лукуллом, который не хотел отдавать Помпею лавры близкой, как ему казалось, победы. Но Помпей сумел переманить на свою сторону бунтующих солдат Лукулла, и это решило дело. Командование Помпея признал и Глабрион. Лукулл вернулся в Рим, еще больше ненавидя Помпея, а Помпей стал готовиться к новой войне. Он сумел склонить на свою сторону парфянского царя Фраата III, пообещав ему часть Армянского царства, и это связало руки Тиграну, который в этих условиях не мог оказать никакой помощи Митридату. Так что Помпею противостоял только один Митридат. Используя опыт, полученный в борьбе с пиратами, Помпей разделил восточную часть Средиземного моря на несколько районов, поставив боевые эскадры охранять их в случае понтийского нападения, а сам с сухопутной армией перешел Тавр, вторгся в Каппадокию и снова занял эту область. Предвидя новую кампанию, Митридат собрал отборную армию из 30 тысяч пехотинцев и 3 тысяч всадников. Но вступить в бой с Помпеем не решился. Он попытался повести с ним переговоры, но римский полководец выставил совершенно неприемлемые для понтийского царя условия, сводившиеся по существу к его полной капитуляции. Митридату пришлось воевать. Но его всадники потерпели поражение, асам он, растерявшись, укрылся в лагере. Помпей окружил лагерь Митридата и 45 дней осаждал его. Наконец, в упорном ночном сражении римляне наголову разгромили войска Митридата. Этому способствовала умелая тактика Помпея, который расположил свои войска так, что луна светила прямо в глаза конникам Митридата, в то время как для римлян они хорошо выделялись, освещенные луной. Сам царь со своей наложницей Гипсикратией и небольшим отрядом сумел прорваться через римские ряды. Он попытался снова направиться в Армению, но на этот раз Тигран, которому угрожали парфяне, не захотел ввязываться в войну с римлянами и отказал тестю не только в помощи, но даже в приеме. Тогда Митридат направился в Колхиду. Зиму 66/65 гг. до н. э. он провел в Диоскурии (Сухуми), а весной перебрался на Боспор. Правивший там от имени Митридата его сын Махар не так давно подчинился Лукуллу и теперь не хотел отдавать власть отцу. Однако Митридат разбил непокорного сына и принудил его к самоубийству. Утвердившись на Боспоре, Митридат стал замышлять новую грандиозную кампанию против римлян, намереваясь пройти через Европу и напасть на Италию с севера. Вернуть же себе Понт он не решался.