Тем временем появилась новая проблема — пираты. Рим разгромил всех своих соперников на Средиземном море. Но вместе с падением могущественных царств исчезли и их флоты, которые боролись с морскими разбойниками. Пираты сделались настоящим бедствием. Народное собрание вручило Помпею власть над флотом на три года и направило на борьбу с пиратами, которые не пропускали в Рим корабли с хлебом. Цены росли, что, впрочем, происходит во время любой революции. К тому же пираты разоряли прибрежные города и поместья. В плен к пиратам частенько попадали богатые римляне. Публий Клодий (о нем речь впереди) был в плену у пиратов, юный Цезарь — тоже. Помпей снарядил 500 кораблей, набрал 125 000 пехоты и 5 000 всадников, разделил море на 13 частей и на каждом участке сосредоточил свои корабли. Почти сразу же большая часть пиратов попала в плен. Но предстояла еще осада укреплений пиратов в Киликии, где морские разбойники хранили свои сокровища. Помпей покончил с пиратами за три месяца, захватив плен более 20 000. Римский полководец не мог отпустить пленных — пираты тут же взялись бы за старое, — но и казнить не стал, хотя история знает немало примеров, когда победитель, набрав слишком много пленных, приказывал их перебить. Помпей принял вполне гуманное решение: поселил пиратов подальше от моря.
В это время Митридат VI Евпатор, тот самый, который казнил 80 000 римских граждан в один день, и с которым воевал Сулла, вновь вторгся в Каппадокию и стал угрожать провинции Азия. Народный трибун Гай Манилий предложил закон о предоставлении Гнею Помпею верховного командования в провинциях Азия, Вифиния и Киликия с правом заключения договоров и союзов, наборов войск и неограниченного получения денег из казны. Подобные полномочия были исключительными: обычно полководец республики не имел права сам объявлять войну или начинать военные действия вне пределов своей провинции. Сенат попытался противодействовать принятию закона, но народное собрание поддержало кандидатуру Помпея. Молодой полководец настиг понтийского царя на берегах Евфрата. Опасаясь, что Митридат может переправиться через реку, римские войска построились в боевой порядок. Сражение произошло ночью. Луна была на ущербе, светила римлянам в спину, свет обманывал. Солдаты Митридата думали, что римляне уже близко, и стали метать в наступавших дротики, но метали впустую, никого не поразив. После этого римлянам не стоило труда опрокинуть противника. Самому Митридату удалось бежать, Помпей пустился следом, передвигаясь по восточным провинциям и разбивая всех, кто встречался ему на пути. Митридат, в конце концов, покончил с собой, перед тем заставив принять яд своих дочерей и наложниц. Смерть Митридата для римлян была равносильна окончательной победе, ибо Рим никому и никогда не прощал смерть своих граждан, и много лет спустя наносил удар по своим врагам. Уничтожение Митридата было куда важнее покорения многочисленных восточных племен и царя Армении.
Помпей получил первый триумф в 26 лет, еще не будучи сенатором — первый подобный случай в Риме. Вообще Помпей трижды справлял триумф: первый за победу над Африкой, второй — над Европой и третий — над Азией. «Так что создавалось впечатление, будто он некоторым образом покорил весь обитаемый мир» (Плутарх).
Победитель Митридата и Тиграна, усмиритель пиратов, очистивший воды Средиземного моря и разгромивший морских разбойников в их логове в Киликии, не сумел справиться с главным врагом — с анархией, охватившей Рим. С одной стороны, Помпей домогался должностей и власти, но когда речь заходила о реформах, он пытался лишь слегка реставрировать старое здание вместо того, чтобы заняться его кардинальной перестройкой. Быть хорошим солдатом — еще не значит быть хорошим политиком, как мы убедились на примере Мария, хотя в Риме политическая и военная карьеры всегда переплетались. То ли Помпей не знал, что надо делать, то ли боялся нарушить устаревшие законы, стремился к вершине и всякий раз останавливался в шаге от нее, сокрушаясь, что не может спокойно жить с женой в деревне. Его жизнь была одним сплошным противоречием.