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