В 74 г. до н. э. сенат послал против пиратов бывшего претора Марка Антония. Ему были предоставлены широкие полномочия, но в отличие от своего более известного потомка Марка Антония, соперника Октавиана, он был не слишком талантлив и потерпел поражение в морском сражении возле Крита в 72 г. до н. э. Вскоре после этого Антоний умер, и в 69 г. до н. э. консул Квинт Цецилий Метелл был отправлен осаждать крепости пиратов на Крите. Он оказался компетентным военачальником, но осада одного укрепленного города следовала за другой, и операция затягивалась. Несмотря на некоторые успехи, проблема с пиратами с каждым годом усиливалась. Как-то раз двое преторов вместе со своими ликторами и всеми спутниками были захвачены во время своей поездки по прибрежному району Италии и за них пираты потребовали выкуп. Была разграблена Остия, порт в устье Тибра.

К 67 г. до н. э. нехватка зерна сделалась критической, и народный трибун Авл Габиний предложил снова создать особую провинцию и предоставить кому-нибудь исключительные полномочия, которые прежде были даны Антонию. Сначала Габиний не упоминал о Помпее как о наиболее подходящем кандидате для этой операции, но ясно, что между этими людьми уже установилась тесная связь. Цицерон утверждает, что Габиний погряз в долгах и весьма вероятно, что Помпей заручился его поддержкой, оказав народному трибуну финансовую помощь. Закон Габиния (Lex Gabinia) был принят народным собранием, и Помпей получил проконсульский империй не только в отношении самого Средиземноморья, но и на 50 миль в глубь суши. Не совсем ясно, был ли империй Помпея равен империю любого другого проконсула, провинция которого частично попадала в пятидесятимильную зону, или же превосходил. Вероятно, последнее утверждение ближе к истине.

Для поддержки Помпею было дано двадцать четыре легата (все они раньше были военными командирами или, по крайней мере, занимали должности претора), кроме того, ему были даны два квестора. Войско Помпея в итоге состояло из флота в 500 военных кораблей, поддерживаемого армией из 120 000 пехотинцев и 5000 кавалеристов. Вместе с ними Помпею были выделены деньги, продовольствие и все прочее, необходимое для проведения военной кампании. Вероятно, значительная часть этих войск была недостаточно подготовлена и плохо дисциплинирована, так как состояла из набранных в спешке рекрутов. В приведенное выше число, возможно, входили также гарнизоны, находившиеся в провинциях, на территорию которых распространялся империй Помпея. Несмотря на большой масштаб действий, это была скорее операция по наведению порядка, а не полномасштабная война. Помпею было необходимо большое войско, чтобы действовать против пиратов во всех направлениях одновременно и лишь небольшой части его армии предстояло принять участие в серьезном сражении.

Хотя Антонию раньше были предоставлены похожие полномочия, Помпей получил в свое распоряжение огромные средства исключительно благодаря личному престижу, а предстоящая операция должна была стать беспрецедентной по своим масштабам. Примечателен тот факт, что подобное назначение обеспечил Помпею народный трибун, чьи полномочия он восстановил во время своего консульства. Примерно так же получал Марий свои назначения в кампаниях против Югурты, кимвров с тевтонами и Митридата. Только несколько полководцев обладало достаточной поддержкой народа, чтобы нарушить традиционную процедуру распределения провинций и средств сенаторами. Вера народа в Помпея была такой сильной, что после его назначения цена на пшеницу на рынке упала. Даже сенаторы, которые не желали наделять одного магистра такой властью — к тому же человека, который своим престижем и богатством уже превосходил всех прочих, — в конце концов признали, что такое назначение было лучшим решением в борьбе с пиратством. Легаты Помпея происходили главным образом из влиятельных знатных семей и таким образом сами представляли заметную силу.

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

Этим людям был дан строгий приказ не преследовать врага за пределами границ порученной им области. Действия самого Помпея не были ограничены какой-либо территорией, а в его распоряжении находилась эскадра из шестидесяти боевых кораблей. Роль остальных легатов в наших источниках подробно не описывается. Некоторые, возможно, были заняты обеспечением снабжения этой масштабной операции. Также весьма вероятно, что они получили в свое распоряжение маневренные эскадры для преследования пиратских кораблей, — примерно такие, как у самого Помпея.

Ранней весной 67 г. до н. э. была начата кампания в западных регионах. Считается, что Помпей очистил эту часть моря за сорок дней. Пираты, которые без всяких помех занимались разбоем в течение десятилетий, были не готовы к подобному натиску и сдались почти без сопротивления.

После краткой остановки в Риме, где один из консулов 67 г. до н. э. тут же сделал попытку подорвать его власть, приказав демобилизовать часть его войск, Помпей отправился в восточные регионы, в самое гнездо пиратов. Здесь, как полагали, предстояла ожесточенная борьба, но пираты и тут оказались застигнутыми врасплох и действовали разобщенно, несмотря на то что раньше помогали друг другу. Одни попытались бежать, но другие (и их становилось все больше) начали сдаваться. Римляне часто прибегали к жестоким мерам, но всегда делали это рационально. В данном случае Помпей решил, что массовые казни окажутся бессмысленными. С пиратами и их семьями обращались довольно хорошо, и многие из тех, кто сдался, принялись снабжать римлян сведениями, которые использовались для планирования операций против других пиратских главарей.

Когда распространилось известие о том, что римляне вполне сносно обращаются с пиратами, число готовых сложить оружие сильно возросло. Помпей заранее подготовил осадную технику для захвата укрепленных городов вдоль гористого побережья Киликии, но обнаружил, что она ему не понадобится: пираты сдавались, едва узнав о его приближении. Иногда пираты пытались вступать в сражения, но быстро терпели поражения. Флор описывает, как судовые команды бросали весла, оружие и хлопали в ладоши — таким образы пираты сигнализировали о том, что сдаются, — почти сразу же, как только видели, что приближаются римские галеры.

На этот раз кампания длилась сорок девять дней. Войско Помпея захватило 71 корабль, потом ему передали еще 306 кораблей. Около 90 из них являлись военными и были оснащены корабельными таранами. В соответствии с римской традицией в честь этой победы была сделана надпись, в которой прежде всего перечислялось количество трофеев. В ней говорилось, что за всю кампанию было захвачено 846 судов, хотя эта цифра, возможно, включала даже крошечные суденышки.