Сулла, ставший полновластным правителем Рима, сумел по достоинству оценить полководческий талант своего верного приверженца. Гней Помпей посылается с войсками на Сицилию, куда с флотом ушел Карбон. Диктатор был пленен и казнен по приказу Помпея.

После этого Сулла посылает Гнея Помпея на север Африки, где собирал войска Домиций, еще один противник Суллы. Помпей покинул остров Сицилия с шестью легионами, которые погрузились на 120 боевых кораблей. Флот сопровождало 800 судов, груженных оружием, продовольствием и боевыми машинами.

На африканской земле сулланский полководец разбивает в сражении 20-тысячное войско Домиция. Он подчиняет новому правителю Рима местные провинции и Нумидию. При возвращении на берега Тибра благодарный Сулла приказал встретить Гнея Помпея с триумфом, утвердив данное ему легионерами прозвище Магнус, что означало Великий.

Смерть Луция Корнелия Суллы в 78 г. до н. э. вновь повергла Рим в междоусобицу. Гней Помпей выступил против Лепида, попытавшегося силой оружия заполучить единоличную власть. В 73–72 гг. до н. э. воюет против марианца Сертория (был убит заговорщиками во время застолья) в Испании, которая «возвращается» Риму. В 71 г. до н. э., вернувшись с легионами с Пиренеев, участвует в истреблении остатков (5 тысяч человек) армии Спартака, разгромленной в битве с легионами Красса.

Помпей приписал себе победу и над Серторием, и над Спартаком. Он донес римскому сенату: «Красс выиграл битву, а я с корнем вырвал войну». Став консулом вместе с Крассом, Гней Помпей добивается отмены ряда законов Суллы и восстановления власти народных трибунов.

Вскоре после этих событий Средиземноморье захлестнула невиданная волна морского разбоя. Целые флотилии пиратов, главной базой которых стала Киликия, перекрыли все морские торговые пути, совершая грабительские набеги и на побережье. Так было разграблено до 400 прибрежных городов.

В Вечном городе резко возросли цены на продовольствие, прежде всего на хлеб, большая часть которого доставлялась морем. К тому же пираты по многим причинам ненавидели римлян, относясь к ним с особой жестокостью. Все это переполнило чашу терпения римского сената.

В 67 г. до н. э. сенат принимает постановление, по которому Гней Помпей Великий получает на три года чрезвычайные полномочия, чтобы покончить с пиратством в Средиземноморье. Народное собрание утвердило законопрект. Помпею разрешили вести военные действия в 50-мильной береговой зоне, снарядить 500 военных кораблей, набрать 120 тысяч тяжелой пехоты и 5 тысяч всадников. Его помощниками стали 24 сенатора.

Помпей Великий действовал в войне против пиратов как подлинный стратег. Он разбил Средиземное море на 13 частей. В каждой из них действовал отдельный отряд кораблей, в основном либурн, отличавшихся хорошими мореходными качествами и маневренностью. Пиратские суда стали захватываться в большом количестве. За 40 дней от пиратов были очищены Тирренское и Ливийское моря, воды вокруг островов Сардиния, Сицилия и Корсика.

После этого Гней Помпей решил провести операцию против центра пиратства в Средиземноморье – Киликии. Туда он отправился во главе эскадры из 60 кораблей. Гнездо пиратства было разгромлено за несколько недель. Помпей приказывал захватывать суда морских разбойников, а тем из них, кто добровольно помогал римлянам бороться со своими собратьями, даровали свободу и жизнь.

В Киликии римские войска и флот подвергали осаде укрепленные города и острова, на которых базировались пираты. Около крепости Коракесий (вблизи турецкого города Аланья) состоялось настоящее морское сражение с киликийскими пиратами. По сильно преувеличенным сведениям, у Коракесия было потоплено сыше 1300 и захвачено 400 пиратских кораблей, погибло 10 тысяч пиратов, а две тысячи попали в плен. После этой операции, не имеющей аналогов в мировой истории, которая проводилась под руководством триумфатора Гнея Помпея Великого, 15 лет мореходство в водах Средиземного моря было безопасным.