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