Składała się ona z około 2 tysięcy różnego rodzaju jednostek! Na ich pokładach znajdowało się kilkadziesiąt tysięcy ludzi. Byli taką potęgą, że uczestniczyli w lokalnych wojnach jako pełnoprawni sprzymierzeńcy.
W roku 67 p. n. e. trybun ludowy Aulus Gabiniusz zaproponował przyjęcie pakietu specjalnych praw, dzięki którym miano oczyścić Morze Śródziemne z piratów (tzw. lex Gabinia). Na ich mocy Pompejusz stał się nauarchą – urzędnikiem odpowiedzialnym za sprawy bezpieczeństwa żeglugi na tym akwenie. Ale nie tylko. Jego władza rozciągnięta została także na tereny przybrzeżne. A wszyscy zarządcy prowincji i władcy państw sprzymierzonych z Rzymem, mieli udzielić mu wszelkiej potrzebnej do realizacji zadania pomocy.
Twierdzono potem nieraz, że aby oczyścić Morze Śródziemne z piratów, Pompejusz otrzymał nieograniczony budżet. Miał przecież w końcu uratować obywateli Rzymu przed głodem, a to nie miało ceny. Niektórzy uczeni jednak powątpiewają.
Pewne jest, że Pompejusz miał do dyspozycji ogromną kwotę 6 tysięcy talentów attyckich srebra (każdy z nich to około 24 kilogramy srebra!), 500 okrętów, w większości ciężkich trój i pięciorzędowców, 120 tysięcy piechoty oraz 4 tysiące jazdy.
Wyczuleni na punkcie władzy i swojej wolności Rzymianie doby republiki, widząc jaka potęga dostała się w ręce jednego człowieka, mówili o nim złośliwie, że dzięki niej szybko „z nauarchy może się stać monarchą.”
Zwycięska legenda
Pierwszym ruchem Pompejusza było zapewnienie nieprzerwanych dostaw zboża do Rzymu. W tym w końcu celu został nauarchą. „Choć pogoda nie sprzyjała żegludze, przeprawił się na Sycylię, zbadał wybrzeża Afryki, zabrał flotę na Sardynię i zostawił garnizony lądowe i sił morskich na straży tych trzech spichrzów państwa (…) Obu mórz Italii strzegły wielkie floty i potężne armie.” - donosi Plutarch.
Operację morską skoordynował Pompejusz z działaniami lądowymi. Aby to usprawnić, cały teren operacji antypirackiej został podzielony na 25 okręgów, którymi zarządzali legaci podlegli nauarsze. Działania przeciw morskim rabusiom toczyły się więc równocześnie na lądzie i morzu. Uważa się, że był to jeden z najważniejszych czynników zapewniających rzymskiemu wodzowi zwycięstwo.
„Jego siły były rozciągnięte, zagrażając bandom piratów z wszystkich stron. Szybko ich przez to pojmano i sprowadzono na ląd. Tych, którzy się wymykali, zapędzono w stronę Cylicji jak pszczoły do ula. Pompejusz przygotował się do uderzenia na nich, biorąc sześćdziesiąt najlepszych okrętów” - relacjonuje Plutarch.
Wydawać by się mogło, że atak na Cylicję będzie najtrudniejszą częścią operacji antypirackiej rzymskiego wodza. Tamtejsi rozbójnicy stawiali opór od dawna i spodziewano się, że łatwo nie sprzedadzą swoich skór. Tymczasem doszło do zaskakującej sytuacji.
Niektóre starożytne relacje donoszą bowiem, że likwidacja cylicyjskich piratów odbyła się w ogóle bez rozlewu krwi. Większość z nich poddać się miała Pompejuszowi bez walki, sparaliżowana poprzedzającą go legendą.
„Jego sława i zdecydowanie wzbudziły popłoch wśród piratów. Licząc na to, że będzie do nich życzliwie nastawiony, jeśli nie będą walczyć, poddali się najpierw ci, którzy opanowali Kragos i Antikragos, najpotężniejsze warownie, po nich zaś ci, którzy żyli w górach Cylicji, a później wszyscy pozostali.” - mówi jedno ze sprawozdań z przebiegu działań.
W rzeczywistości nie było aż tak łatwo. Nawet jeśli piraci cylicyjscy wystraszyli się Pompejusza, to jednak w rozpaczliwym odruchu samoobrony, podjęli rzuconą im przez niego rękawicę. Do największego starcia zbrojnego na morzu doszło pod Korakesion (dziś Alanya w Turcji).
Flota rozbójników została w niej niemal doszczętnie rozgromiona. Było to zwycięstwo tym większe, że piraci dysponowali w tym starciu przewagą liczebną. Wystawili do walki około tysiąca okrętów przeciw dwustu rzymskim (chociaż te ostatnie były cięższe i lepiej uzbrojone). Resztki pobitej floty schroniły się w okolicznych portach.