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

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

Характер римского господства изменился, когда высшее военное командование в Средиземноморье получил в свои руки Помпей. Это назначение стало поворотным моментом не только в истории римской экспансии, но и на долгом пути Рима от республики к монархии.

В силу сотрудничества Митридата с общинами, которые традиционно добывали средства к существованию морским разбоем, особенно с критянами и киликийцами, Третья Митридатова война с самого начала была тесно связана с борьбой Рима против пиратов. В античном Средиземноморье морские экспедиции с целью грабежа, которые римляне считали пиратством, от «регулярных» боевых действий отделяла очень тонкая черта (если она вообще была). Зачастую одно сообщество, желая отомстить за обиды, провозглашало акты возмездия, после чего совершало набеги и захватывало богатства обидчиков. Разбойные нападения часто организовывали каперы, пользовавшиеся хаосом военного времени; часто они сопровождали армии и поддерживали их действия атаками на корабли и прибрежные поселения. Но в некоторых землях, таких как Иллирия, Этолия, Крит и Киликия, набеги на тех, кто не находился под защитой договоров о ненападении (asylia), происходили регулярно. Грабеж, как и завоевание, считался законным способом получения прибыли, проистекавшим из военного превосходства и требовавшим благоволения богов. Пиратская добыча состояла прежде всего из ценных вещей и пленников, которых продавали в рабство или возвращали за выкуп их семьям или городам. Как только набег завершался, пираты превращались в торговцев, направляясь для продажи захваченного добра в ближайший крупный порт или домой. Существовала пословица: «Три сквернейшие К — Каппадокия, Крит и Киликия»; она показывает, сколь дурной славой пиратов и бандитов пользовались жители этих областей.

В конце II — начале I века до н. э. морским путям, связывавшим Италию с рынками, поставщиками зерна и ресурсов в Северной Африке, Греции, Малой Азии и на Ближнем Востоке, стали угрожать частые нападения. Подъем пиратства стал результатом действия различных факторов: упадка Родоса как военной силы, в прошлом обеспечивавшей безопасность Восточного Средиземноморья, сотрудничества между Митридатом и пиратами, потребности критян компенсировать убытки из-за прекращения их найма в царские армии усилением пиратских действий и, возможно, повышения спроса на рабов в сельском хозяйстве и ремесле. Сообщается, что на Делосе за один день могли продать до 10 000 рабов, и зачастую эти люди были жертвами пиратов.

Первая римская кампания против пиратов началась в 74 году до н. э., когда претор Марк Антоний был наделен полномочиями для того, чтобы очистить моря от пиратов. Она обернулась полным провалом, а реквизиция средств у провинциального населения для ведения войны укрепила недовольство греков римской властью. Марк Антоний умер на Крите в 71 году до н. э., не добившись ничего. В историю он вошел как Критский, но не в честь победы над критянами («Завоеватель Крита»), а в ироническом смысле — в напоминание о его поражении, так как с латинского слово Creticus можно перевести как «меловой». Однако римляне были твердо намерены решить проблему пиратства.

Когда в 70 году до н. э. в Рим прибыла делегация Критской федерации для обсуждения условий мирного соглашения, сенат потребовал уплатить огромную сумму в 4000 талантов, выдать Риму военные суда и 300 заложников, включая их военных вождей. Критяне разделились: старшие граждане были склонны принять эти требования, но молодые люди, с детства приученные к боям и грабежам, одержали победу. Двадцать четыре тысячи молодых критян сражались с римлянами под предводительством Ластена Кносского и Панара из Кидонии с 69 до 67 г. до н. э. Римскими войсками командовал Квинт Цецилий Метелл, прошедший остров с запада на восток; он награждал тех, кто соглашался сотрудничать, стирал с лица земли пиратские крепости вроде порта Фаласарна и жестоко расправлялся с городами наподобие Элевтерны и Кносса. К концу этой войны социальная и политическая система, которая существовала на острове с VII века до н. э., была уничтожена, и на Крит хлынула первая волна римских и италийских предпринимателей.

В 67 году до н. э., еще до завершения Критской войны, Помпею для ведения тотальной войны против пиратов были выделены огромные силы. Закон Габиния (lex Gabinia), устанавливавший пределы чрезвычайных полномочий Помпея, расчистил путь к становлению монархической власти четырьмя десятилетиями позднее. Его полномочия были шире, чем у всех других римских полководцев (высший империй — imperium maius); они длились три года и давали Помпею контроль над морем и землей на расстоянии 50 миль от берега. Такой империй нарушал два фундаментальных принципа римского устройства: ни одна должность не должна замещаться более одного года и каждый магистрат должен иметь по меньшей мере одного коллегу. Помпею были приданы 13 помощников (легаты, или посланники), которые предвосхищали более поздних legati Augusti pro praetore — представителей императора в провинциях, где размещались римские войска. Оппозиция консервативных кругов в сенате в конце концов была сломлена при помощи Гая Юлия Цезаря и плебейского трибуна Авла Габиния, предложившего данный закон.

Помпей и его легаты начали систематически уничтожать крепости и флоты пиратов с запада к востоку. Через 40 дней между Испанией и Италией не осталось ни одного пиратского корабля. Затем кампания сместилась к двум главным центрам пиратства — Криту, где уже действовал Метелл, и к Киликии. Помпей, сочетая военные действия с переговорами, вынудил киликийских пиратов отказаться от их традиционного промысла, и через десятилетие осталась лишь горстка морских разбойников.

По-видимому, во время своего пребывания в Киликии Помпей разработал план умиротворения Востока в пределах Римской империи. Многих пиратов он поселил в городе Солы, который переименовал в Помпейополь. Это было историческое решение не только потому, что полководец милостиво обошелся с бывшими врагами, которым был предложен альтернативный источник средств — сельское хозяйство, — но и потому, что впервые римский военачальник основал город, названный в свою честь, следуя традициям эллинистических царей. После этого успеха в войне, которая — по словам Цицерона — была подготовлена зимой, начата весной и завершена летом, Помпею было предложено победить там, где потерпел поражение Лукулл. Его полномочия были расширены, и он был направлен на войну против Тиграна и Митридата.