Rome nonetheless dispatched a force in 103 B.C. to cow the pirates, and established a province in eastern Cilicia, the more level and fertile area of the region, but was unable to permanently destroy the pirate bases in the west. The pirates expanded their operations throughout the first decades of the first century B.C., becoming one of the major naval powers of the Mediterranean. This power made them potential allies for many enemies of Rome, and both Mithridates and the rebel Roman general Sertorius, in Hispania, made overtures to and cooperated with the Cilician pirates.During the Third Servile War, Spartacus would negotiate with the Cilician pirates as potential allies in his struggle against the Roman Republic, but the importance of slaving to the Cilician pirates made any alliance between the pirates and a slave rebellion one fraught with tension and potential for betrayal.
The Cilicians of the First Century BCE were a multi-ethnic nation, composed of Greek, Syrian and Isaurian descent, though the country was Hellenized culturally since the time of Alexander the Great.