Попытка Рима уничтожить морской разбой с помощью военного флота под командованием Публия Сервилия окончилась неудачей. Пиратские либурны были маневреннее, чем тяжелые корабли римлян. Но как только военные корабли скрывались, сыны Киликии вновь выходили, захватывали их суда и брали пленных. Это сказывалось на жизни города. В 67 году до н. э. положение с хлебом в Риме столь ухудшилось, что сенат вынужден был поручить Гнею Помпею возглавить борьбу с пиратами и предоставил ему особые полномочия. Операция считалась настолько сложной, что для ее осуществления Помпей попросил дать ему три года. Он показал себя умелым флотоводцем. По его приказу было построено 500 либурнов, то есть кораблей такого же типа, как и те, на которых плавали пираты. Первоначально Помпей избрал местом своих действий западную часть Средиземного моря. Он разбил этот район на 13 округов и для каждого выделил командира, предоставив в его распоряжение соответствующее количество Кораблей. Сам полководец принял командование над Центральным флотом, который занял выжидательную позицию между Африкой и Сицилией.
Кроме флота, Помпей собрал армию из 12 тыс. пеших легионеров и 5 тыс. всадников. Армия должна была бороться с пиратскими поселениями на побережье. Вся операция была им так хорошо продумана и организована, что уже через 40 дней он смог доложить сенату, что в западной части Средиземного моря с пиратством покончено.
Одержав эту победу, Помпей отправился на восток Средиземноморья, в район, где действовали киликийские пираты. Очевидно предупрежденные об успехах римского полководца, но уверенные в своем превосходстве, они вступили в открытый бой с римским флотом у Коракесия и были разбиты. По дошедшим до нас сведениям, морские разбойники потеряли в этом бою 1300 кораблей, 400 — достались победителям; 20 тыс. пиратов были взяты в плен, 10 тыс. — погибли.
Победитель показал себя снисходительным и дальновидным: он приказал казнить лишь несколько сот главарей. Остальных пиратов Помпей поселил на безлюдном побережье восточной части Средиземного моря, предоставив им возможность заниматься земледелием.
После этой крупной победы Помпея Кипр, Крит, Менорка и Мальорка добровольно признали господство Рима на море. Казалось, что отныне с пиратством в водах Средиземного моря покончено. Но и на сей раз пиратство выжило и лишь временно переместилось на окраину Римской империи.
Иллирийцы, жившие на далматинском побережье Адриатики, продолжали оставаться грозными разбойниками. Однажды, когда римская миссия обратилась с жалобой к владычице Иллирии по поводу захвата ее подданными римских кораблей, царица заявила: "Я не могу запрещать своим людям извлекать пользу из моря". Пунийские и греческие пираты также продолжали охотиться за римскими торговыми кораблями, и скоро пиратство вновь обрело прежнюю силу и превратилось в большую опасность для Рима.
