A lovagrendi üzletembereknek a legérzékenyebb veszteséget, a Kis-Ázsia területén dúló háború mellett, a kalózok tengeri uralma, szinte az egész Földközi-tengerre kiterjedő garázdálkodása okozta. A Kr. e. 70-es évek folyamán a tengeri rablók a Földközi-tenger keleti felében szinte lehetetlenné tették a hajózást, a kereskedelmi forgalmat, s nemcsak a szíriai, kis-ázsiai és görög tengerpart vidékének és a szigetvilágnak lakóit tartották állandó rettegésben, hanem betörtek Szicília és Itália területére is, raboltak-zsákmányoltak, sőt még az ostiai kikötőben állomásozó római flottát is megtámadták (vö. RÓR 28-29).
A keleti gabonaszállítmányok megritkulása miatt nyugtalanság lett úrrá az ellátásáért aggódó római plebs körében. A Spartacus-felkelés idején fellépő gazdasági nehézségek csak fokozták ezt a hangulatot. Rómát ebben az időben elsősorban a Verres által Szicília területén összeharácsolt gabonával látták el. Jellemző a helyzetre, hogy a proscriptiók alatt és a későbbi spekulációi révén példátlanul meggazdagodott Crassus azzal fokozta leginkább népszerűségét, hogy 10 ezer asztalnál vendégelte meg Róma lakosságát, s három hónapra elegendő gabonát osztott ki a város szegényei között.

M. Antonius hadjárata (Kr. e. 102) óta Róma ismételten kénytelen volt fellépni a kalózok ellen. P. Servilius Vatia hadjárata (Kr. e. 78-75 között) jelentős területeket szerzett Rómának Kis-Ázsia déli partján, a kilikiai kalózok tengeri uralmát azonban szárazföldi támaszpontjaik elfoglalása után sem tudta letörni. Sőt tevékenységük középpontját nyugatabbra, Kréta szigetére tették át. Itt mértek Kr. e. 71-ben döntő vereséget a fiatalabb M. Antoniusra, akit Rómában megbélyegzésül láttak el a Creticus melléknévvel. A szégyenletes helyzetben a senatus (Kr. e. 69-ben) Q. Caecilius Metellust bízta meg a krétai kalóztámaszpont felszámolásával; azonban az általános helyzetben Metellus helyi sikerei ellenére sem állt be változás.

A kalózok tengeri uralmának megtörése, a tengeri kereskedelem biztonságának, a Földközi-tenger partvidéke nyugalmának helyreállítása méltó feladatnak ígérkezett Pompeius számára, hogy hadvezéri becsvágyát kielégítse. A kereskedelmi veszteségei miatt elégedetlen lovagrend, a kenyeréért aggódó plebs és Pompeius befolyásának hatására Kr. e. 67-ben napirendre került Aulus Gabinius néptribunus javaslata, melynek alapján Pompeiust rendkívüli hatáskörrel ruházták fel a kalózok elleni hadjárat vezetésére.
A senatus konzervatív exponensei, Hortensius, C. Calpurnius Piso s különösen Q. Lutatius Catulus a legvégsőkig elmentek a törvényjavaslat meghiúsítása érdekében, de hiába. Pompeius az egész Földközi-tengerre és a partok mentén kb. 75 kilométeres sávra kiterjedő teljhatalmat kapott; 500 hajóból álló flotta, jelentős szárazföldi haderő és 6000 talentumnyi pénzösszeg állt rendelkezésére, továbbá a szövetséges államok és városok támogatása.

Pompeius hadjárata a kalózok ellen meglepően gyors sikerrel járt. A tengert körzetekre osztották, az egyes körzetekben Pompeiusnak alárendelt parancsnokok működtek meghatározott számú hajóval. A Földközi-tenger nyugati medencéjét kb. 40 nap leforgása alatt megtisztították a kalózoktól, s további két hónap alatt megsemmisítették, illetőleg megadásra kényszerítették a keleti vizeken tevékenykedő kalózszervezeteket is. A hadjárat során mintegy 10 000 kalóz vesztette életét, s kereken 20 000 került fogságba.
A hadjárat befejezése után Pompeius győzelmes flottája Kis-Ázsia déli partjainál állomásozott, amikor Rómában C. Manilius néptribunus (66 elején) jól időzített — s a körülményekből következtethetően előzetes megállapodáson alapuló — javaslatot nyújtott be arra vonatkozóan, hogy a Mithridatés ellen folyó háború vezetését bízzák Pompeiusra (lex Manilia). A javaslat mellett fellépett Cicero, a lovagrend szószólója és a fiatal C. Iulius Caesar, a római plebs újdonsült kedvence és reménysége is.