После окончания своего консульского года Помпей на какое-то время ушел в частную жизнь. Но очень скоро ему снова пришлось взяться за государственные дела. В 67 г. до н. э. по закону, предложенному народным трибуном Авлом Габинием, Помпею было поручено вести войну против пиратов. Решение пиратского вопроса было чрезвычайно важно для римлян. Пираты не только опустошали берега Средиземного моря и, грабя суда и уничтожая их экипажи, в значительной степени парализовали средиземноморскую торговлю и препятствовали даже политикоадминистративным связям Рима с заморскими провинциями, но и выступали союзниками злейшего врага Рима Митридата. Дерзость пиратов доходила до того, что они даже добирались до устья Тибра у самых ворот Рима. В 79 г. до н. э. сам Сулла был вынужден обратить внимание на пиратские набеги в восточной части Эгейского моря. В следующем году в Восточное Средиземноморье был послан проконсул П. Сервилии Ватия. Он действовал весьма энергично и добился значительных успехов. Уже в первый год он подчинил ряд пиратских гнезд в Киликии, активны и успешны были его действия и в следующие годы в той же Киликии, Ликии и Исаврии. За все эти подвиги он получил триумф и почетное прозвище Исаврийский.
В 74 г. до н. э. войну с пиратами было поручено вести претору Марку Антонию. В этой войне ему было дано неограниченное командование (
По этому проекту, одному из консуляров, т. е. бывших консулов, предоставлялось такое же неограниченное командование, как ранее Антонию, на все море по эту сторону Геркулесовых Столпов и на расстоянии до 50 миль в глубь суши; при этом командующий мог выбрать себе из числа сенаторов 15 легатов, давим преторский ранг, взять неограниченное количество денег из казны и от откупщиков и снарядить флот из 200 кораблей с правом самому набирать воинов и гребцов. Из-под власти такого командующего были исключены только очень немногие территории, где уже активно и довольно успешно действовали римские командиры, в том числе Крит. Хотя трибун не назвал имя предполагаемого командующего, ни у кого не было сомнения, что речь идет о Помпее.
Вокруг законопроекта развернулась ожесточенная борьба. Из всего состава сената Габиния поддержал только Гай Юлий Цезарь. Начиная свою политическую карьеру в качестве популяра, он сделал ставку на расположение народа, а поскольку в это время народ горячо поддерживал Помпея, то и Цезарь выступил на его стороне. Остальные же сенаторы, опасаясь слишком резкого выдвижения и так уже очень популярного Помпея, решительно выступили против законопроекта. Консул Гай Кальпурний Пизон открыто угрожал Помпею смертью, за что чуть не был растерзан возмущенной толпой. Активный и весьма уважаемый сенатор Квинт Лутаций Катул напрасно взывал к народу с призывом поберечь Помпея и не подвергать его опасностям войны. Но на его риторический вопрос, а кого же можно будет поставить на место Помпея, если с тем что случится, народ единодушно, хотя и с явной издевкой, ответил, что его, Катула. Коллега Габиния Люций Росций Отон предложил дать будущему командующему коллегу, но эта попытка ограничить власть полководца и флотоводца провалилась. Активные действия противников законопроекта привели к роспуску народного собрания, не принявшего никакого решения. Но вскоре собрание было созвано вновь, и оно не только приняло закон, но и расширило полномочия командующего. Теперь он мог иметь уже 24 легата, его военные силы были удвоены до 500 кораблей, 120 тысяч пехотинцев и 5 тысяч конников. После принятия этого закона командующим уже персонально был выбран Помпей.