Для этого Помпей разделил Средиземное и Черное моря на 13 частей и в каждую из них направил эскадру кораблей с соответствующим количеством воинов под командой одного или двух выбранных им помощников из числа сенаторов.
Приведем сделанную Помпеем разбивку морских районов боевых действий и имена поставленных им начальников эскадр (навархов) в каждом из них, которую составил А. Б. Снисаренко на основе анализа отрывочных сведений древних авторов.
1. Тиберий Нерон и Манлий Торкват: Иберийское море (так называли часть Средиземного моря у берегов Иберии, теперь Пиренейского полуострова) и часть Атлантики от устья реки Таг (теперь Тахо) до Балеарских островов.
2. Марк Помпоний: Балеарское и Лигустинское моря – часть Средиземного моря от Балеарских островов до Апеннинского полуострова.
3. Поплий Атилий: побережье Корсики и Сардинии.
4. Плотий Вар: Сицилия и Африканское море – побережье Сицилии и часть Средиземного моря между Сицилией и побережьем Африки.
5. Лентул Маркеллин: североафриканское побережье от Египта до Иберийского моря.
6. Лукий Геллий Попликола и Гней Лентул Клодиан: Тирренское и Адриатическое побережья Италии.
7. Теренций Варрон: западное побережье Греции от Коринфского залива до пролива Отранто (современное название) между побережьями Италии и Албании, а также патрулирование Средиземного моря между Сицилией и Кикладами.
8. Лукий (Корнелий) Сисенна: западное побережье Эгейского моря, побережье Пелопоннеса и Македонии.
9. Лукий Лоллий: Эгейское море со всеми островами.
10. Метелл Непот: южное побережье Малой Азии, Кипр и Финикия.
11. Кепион: западное побережье Малой Азии.
12. Публий Писон: Черное море.
13. Марк Поркий Катон (под началом Писона): Мраморное море.
Грандиозная операция была проведена Помпеем блестяще. Эскадры скрытно направились в заданные районы и в установленный заранее день атаковали главные пиратские базы. Наиболее тяжелой для выполнения оказалась задача, поставленная перед эскадрой Метелла Непота. У южных берегов Малой Азии произошли жестокие сражения с пиратскими флотилиями. Эскадра Плотия Вара отрезала пиратов западной и восточной частей Средиземного моря друг от друга и пресекла попытки пиратских флотилий прийти на помощь своим коллегам по ремеслу.
Сам Помпей возглавил эскадру из 60 кораблей, которая действовала по всему простору Средиземноморья. Сперва Помпей со своей эскадрой остался в Тирренском море и крейсировал между Италией, Сицилией и Сардинией. Взаимодействуя с эскадрами западной части Средиземного моря, Помпей смог разгромить пиратов в этом регионе за 40 дней. Экономическая блокада Апеннин была ликвидирована. Помпей сосредоточил дополнительные силы для уничтожения основного пиратского гнезда в Киликии, куда он и направился со своей эскадрой.
