Собрав силы и снарядив корабли, Помпей разделил все Средиземное море на тринадцать частей, в каждой из которых сосредоточил по эскадре кораблей и сразу как бы захватил в сети пиратские суда. Успевшие прорваться морские разбойники укрывались в своих тайных убежищах в Киликии. Благодаря умелому руководству и энергии Помпея западная часть Средиземного моря, а также водные пространства вокруг Италии, Сардинии, Корсики и Сицилии вскоре были очищены от пи; ратов. Некоторые из пиратских кораблей сдались на милость победителя. Командам этих судов была сохранена жизнь (кроме совершивших какие-либо преступления против Рима).
Самые закоренелые злодеи и главари укрыли своих жен, детей и награбленные богатства в крепостях и тайных убежищах на Тавре, а сами с большим флотом ожидали нападения Помпея у Коракесия в Киликии (это была неприступная крепость, расположенная на отвесной скале). В морском сражении пираты были разбиты наголову. Римляне захватили много кораблей противника.
Затем Помпей приступил к осаде крепостей и убежищ разбойников. Последние, видя, что дальнейшее сопротивление невозможно, решили сдаться. В плен было взято более 20000 пиратов, не считая их семей. Помпей не решился их казнить, В то же время он не рискнул отпустить пленников на свободу, позволив им, таким образом, вновь объединиться в шайки. Поэтому Гней приказал переселить всю эту массу людей в местность, расположенную вдали от моря, и там приучить их жить в городах и обрабатывать землю. Часть пиратов по приказанию Помпея приняли маленькие и малолюдные городки Киликии, большинство же разбойников он переселил в город Диму в Греции и во вновь основанный им город Помпейополь (на месте города Солы в Киликии). Когда в Рим пришло известие, что война с пиратами окончена, один из народных трибунов предложил законопроект о передаче Помпею всех провинций и войск на Востоке (в Малой Азии), которыми командовал Лукулл, сражавшийся в то время против Митридата и Тиграна. Этот закон совершенно незаслуженно лишал Лукулла награды за совершенные им подвиги и являлся не чем иным, как подчинением всей римской державы власти одного человека — Помпея. Несмотря на яростное сопротивление оптиматов, предложение трибуна было утверждено народом. Так простым постановлением Народного Собрания Помпей был облечен властью, которой в свое время Сулла добился путем войн и насилий. Отправившись в провинции, Помпей сразу стал отменять все распоряжения своего предшественника Лукулла. Он отстранил от командования последнего, оставив в его распоряжении 1600 солдат. Обиженный и раздраженный Лукулл уехал в Италию, а Помпей, взяв командование в свои руки, выступил против царя Понта Митридата. Царь понтийский, располагавший армией в 30000 человек пехоты и 2000 конницы, не решался дать сражение римлянам. Помпею удалось окружить Митридата и осадить его лагерь. Царь выдерживал осаду в течение 45 дней, а затем, перебив больных и раненых, незаметно бежал с лучшей частью войска. Помпей, однако, настиг царя на реке Евфрат. Боясь, как бы враги не успели раньше его переправиться через водный рубеж, Помпей тотчас же напал на их стоянку. Митридат потерпел полное поражение: более 10000 его солдат пали, лагерь стал добычей победителей. Сам царь успел прорваться с 800 всадниками сквозь ряды римлян. Однако этот отряд быстро рассеялся, и Митридат Евпатор принужден был продолжать бегство только с тремя спутниками. Беглецы, наконец, прибыли в крепость Синопу, где находилась царская сокровищница. Митридат роздал часть сокровищ и драгоценных одежд своим спутникам и дал каждому из них смертоносного яду, чтобы никто живым не попался в руки врага.
Из Синопы Митридат направился к армянскому царю Тиграну, но тот из страха перед Помпеем отказал ему в убежище и даже объявил награду за его голову. Тогда царь Понта, миновав истоки реки Евфрат, направился в Колхиду.
Между тем Помпей, двигаясь за Митридатом, вошел с войском в Армению. Царь, старый Тигран, только что разбитый Лукуллом, принял римлян в своей столице, а сам отправился к Помпею.
Явившись в лагерь римского полководца, армянский царь снял свою корону и собирался, по восточному обычаю, пасть на колени и просить пощады. Помпей, однако, ласково обнял Тиграна, предложил ему место рядом с собой и во время беседы сообщил царю необременительные для Армении условия мира. Только присутствовавший здесь же сын старого царя, молодой Тигран, держал себя вызывающе и дерзко по отношению к римскому полководцу. Тогда Помпей велел схватить его и держать в тюрьме до дня своего триумфа.