A la mort (naturelle) de Sylla en - 79, le consul de - 78, Marcus Aemilius Lepidus veut lui succéder et pour commencer il propose le rappel des proscrits, la restitution du droit de cité à ceux qui l’avaient perdu ainsi que la restitution des terres confisquées. Le second consul Quintus Lutatius Catulus oppose son intercession. Lepidus part en Etrurie soutenir la révolte des habitants de Faesulae contre les colons de Sylla (vétérans qui avaient bénéficié de terres confisquées), il fait venir les enfants des proscrits et il tient la Gaule cisalpine avec une armée commandée par Brutus. En - 77, il envoie un ultimatum au Sénat qui vote le senatus consultum ultimum, une loi martiale et charge Catulus comme proconsul de réprimer Lepidus. Celui ci marche sur Rome. Catulus envoie Pompée qui a rallié l'aristocratie, attaquer Brutus qui le capture et l'élimine. Lepidus est arrêté au pont Milvius et à la nouvelle de la mort de Brutus, il part en Sardaigne et meurt naturellement peu après.
En - 70, Crassus et Pompée sont nommés consuls de façon tout à fait illégale. Crassus finit juste sa préture et Pompée est trop jeune pour être candidat. Les consuls annulent les réformes de Sylla, rétablissent le tribunat de la plèbe et la censure.
Pendant toutes ces années de luttes intestines, la police des mers était fort mal assurée. Le Sénat envoie en expédition Servilius et Marcius en Cilicie et Metellus en Crète, Gaius Triarius, un lieutenant de Lucullus, fortifie l'île de Délos, mais rien n'y fait, les navires marchands sont pillés mais aussi les ports et les îles et les pirates n'hésitent pas à rançonner des généraux romains et de plus, ces pirates aident Mithridate à l'occasion. Le préteur Marcus Antonius est chargé par le Sénat du titre de curator tuendae totius orae maritimae, c'est à dire de faire la police sur toutes les côtes méditerranéennes, au moment ou les pirates font communiquer Mithridate et Sertorius. Antonius dispose de l'imperium infinitum (illimité) et il est vaincu en Crète et meurt prisonnier. Rome a perdu la maîtrise de la mer et plus de mille navires pirates gênent la navigation et le trafic et menacent Rome de disette. En - 67, le tribun Aulus Gabinius fait voter la Lex Gabinia qui donne à Pompée l'imperium sur l'ensemble de la Méditerranée, c'est à dire "jusqu’aux colonnes d’Hercule et sur terre, en tous lieux, jusqu’à quatre cents stades (environ 72 kilomètres)" nous dit Plutarque, dans le but d'éradiquer la piraterie.
Pompée a le pouvoir de lever 20 légions et d'armer 500 navires, de nommer 24 légats disposant de leur propre imperium sur une zone limitée et de grandes sommes d'argent sont à sa disposition. C'est tout à fait nouveau ! En fait, il dispose de 270 navires et de l'aide des Rhodiens. Son plan est simple, il verrouille toutes les mers et tous les golfes de la Méditerranée au Pont-Euxin et s'occupe personnellement de la Cilicie, vainc facilement les pirates devant Coracesium et les éloigne de la mer en les fixant à l'intérieur des terres. Le bilan est positif : aucune perte de navire et la mission est accomplie en quarante neuf jours et selon Pompée, 846 navires pirates sont pris ou détruits. Les prisonniers Ciliciens vont introduire à Rome le culte de Mithra.