Помпей блистательно оправдал ожидание народа; ни в одной из своих войн он не обнаруживал таких способностей и такой деятельности, как в войне с морскими разбойниками. Впрочем, он обладал такою властью, которая могла сокрушить все. Его военный план был составлен мастерски. Вся война продолжалась не более трех месяцев и была скорее облавой, чем настоящей войной, так как пираты не решались вступать в сражение и, не имея возможности спасаться бегством, большей частью сдавались вместе со своими кораблями, женами и детьми. Только самые отчаянные и преступные из них спаслись вместе со своими семействами и сокровищами в крепостях Тавра и вышли против Помпея на мысе Коракезион, на западной границе дикой Киликии. Они были разбиты и покорились. Так как Помпей щадил покорившихся и обращался с ними мягко, то они указывали ему разбойничьи притоны в горах, так что он избавился от продолжительной и опасной войны в горах. Таким образом, пиратство было совершенно уничтожено. Пленные пираты были поселены в разных местах: лучшие – в городе Содой, в Киликии, получившем теперь имя Помпейополиса, другие в Адане, Мадле и Эпифании – в Киликии же, немногие из остальных – в Димэ, в Ахаии и в Калабрии. В то время когда Помпей был еще занят наведением порядка в южной части Малой Азии, городские общины острова Крит отправили к нему послов с просьбой принять их под свое покровительство, так как они надеются, что он обойдется с ними лучше, чем проконсул Кв. Метелл, который уже второй год успешно ведет войну на острове, но обращается с покоренными жителями весьма жестоко. По закону Габиния власть Помпея распространялась, конечно, и на Крит; но Метелл еще с прошлого года вел здесь самостоятельную войну, не принадлежал к легатам Помпея и почти уже окончил покорение острова; он мог требовать, чтобы Помпей воздержался от вмешательства в критские дела. Но честолюбие Помпея нашло здесь новый удобный случай пожать там, где он не сеял; он принял критян под свое покровительство и послал на остров своего легата Д. Октавия, чтобы запретить Метеллу вести войну и принять взятые им города. Так как Метелл не послушался приказания Помпея и продолжал осаждать и брать города, то Октавий призвал сюда стоявшего в Ахаии легата Помпея, Л. Корнелия Сизенну, с войском, и таким образом между войсками Метелла и Помпея началась настоящая война. Надо было опасаться междоусобицы; но Помпей прекратил этот раздор, за который его порицали многие из его друзей, так как он уже рассчитывал, что его пошлют на место Лукулла против Митридата.

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