Между тем Сулла еще ничего не знал об этих событиях. При известии, что Помпеи вынужден действовать против столь превосходящих сил противника, Корнелий Сулла испугался за его судьбу и немедленно выступил на помощь. Когда Помпеи узнал о приближении сулланской армии, он приказал выстроить войско для торжественной встречи главнокомандующего, чтобы произвести на него впечатление. Гней Помпеи рассчитывал на великие почести со стороны Суллы, но получил награду еще большую, чем ожидал. Приветствуя Суллу, Помпеи назвал его императором. Сулла, отвечая Помпею, также назвал его императором. Никто не ожидал, что Сулла даст столь высокое звание молодому человеку. Однако не только при первой встрече, но и впоследствии диктатор старался оказывать Помпею особые знаки внимания, отличая его среди множества других людей. Сулла вставал и обнажал голову при появлении Помпея (почесть, которую всесильный властитель оказывал только немногим).

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

Некоторое время спустя пришла весть о том, что вожди народной партии вновь собирают силы для борьбы. Так, один из них, Перпенна, укрепился в Сицилии, стараясь превратить остров в опорный пункт для вторжения в Италию; Карбон с флотом также крейсировал вдоль берегов Сицилии, а третий вождь демократов - Домиций - высадился с войском в Африке, куда собрались изгнанники, преследуемые Суллой.

Против них Сулла послал Помпея. Последнему вскоре удалось отобрать Сицилию у Перпенны (который бежал) и захватить в плен Карбона. Боясь, чтобы диктатор не заподозрил его в симпатии к демократам, Помпеи казнил захваченных в плен видных противников Суллы. Рассказывают, что он заставил пленного Карбона, человека, знатного, трижды избиравшегося консулом, в оковах стоять перед судом, а затем велел его предать казни. Менее известным демократам Помпеи, если это не могло возбудить подозрений Суллы, позволял укрываться, а некоторым даже помогал бежать. Помпеи решил наказать жителей сицилийского города Гимеры за то, что они поддерживали демократов. Один из гимерцев - Сфений сказал:

- Ты, Помпеи, поступишь несправедливо, если отпустишь виновного, а погубишь ни в чем неповинных людей.

- Кого же ты считаешь виновным? - спросил Помпеи.

- Себя,- отвечал смело Сфений,- ведь это я убедил сограждан выступить.

Помпеи, восхищенный смелостью и благородством этого человека, даровал ему прощение. В то время как Помпеи улаживал сицилийские дела, пришло письмо от Суллы с приказанием немедленно отбыть для военных действий против Домиция в Африку, где последний сконцентрировал большие силы. Окончив приготовления, Помпеи с шестью легионами отплыл к берегам Африки и вскоре высадился с частью армии в Утике. Другая часть войска прибыла в Карфаген, где на ее сторону перешло около 7000 вражеских воинов. По прибытии Помпея в Утику произошло забавное происшествие: один из солдат случайно обнаружил денежный клад. Весть о находке моментально распространилась по всему лагерю. Тогда остальные легионеры бросились искать клады, будто бы зарытые карфагенянами еще во время осады их города римлянами. Много дней Помпеи ничего не мог поделать с солдатами, которые, словно одержимые, перекопали землю в расположении лагеря. Военачальнику ничего не оставалось делать, как смеясь наблюдать за бессмысленной работой тысяч обезумевших людей. Наконец, солдаты утомились и предложили Помпею вести их, куда ему угодно. Помпеи поспешно выступил против Домиция. Невзирая на непогоду и водную преграду, отделявшую его от неприятеля, Помпеи ночью смело и неожиданно напал на врага. В жестокой битве солдаты Гнея одолели противника, захватив его лагерь. Сам Домиций пал в бою. После этого все города в Африке и местные цари подчинились власти Помпея. Возвратившись в Утику, Помпеи получил письменное приказание диктатора немедленно распустить войско, а самому с одним легионом ожидать на месте преемника по командованию. Это вызвано было тем, что Сулла получил ложное известие об измене Помпея. Помпеи не решался явно выразить свое недовольство. Солдаты же открыто заявили, что не желают подчиняться приказу. Помпеи стал уговаривать солдат смириться, а они в свою очередь предлагали ему остаться начальником и вести их против Суллы. С великим трудом Помпею удалось успокоить солдат и заставить их разойтись. Когда Сулла узнал истинное положение дел, то поспешил любезно встретить Помпея и преподнес ему титул "Великого".

По возвращении в Рим Помпеи потребовал триумфа. Сулла долго не желал предоставить ему этой почести, но все же вынужден был согласиться.

В последнее время диктатор изменил свое благосклонное отношение к Помпею, завидуя его славе и возрастающему могуществу.

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

После смерти Суллы один из консулов, Лепид, собрал сторонников демократов и поднял восстание против сената. Помпеи, присоединившийся к партии оптиматов, был назначен главнокомандующим в войне против повстанцев.

Помпеи всюду одолевал своих врагов. Только у города Мутины ему пришлось задержаться, чтобы разбить Брута - одного из полководцев Лепида. (Этот Брут был отцом Марка Брута, который впоследствии участвовал в заговоре против Юлия Цезаря.) Лепид, узнав о поражении Брута, бежал из Италии, переправившись на остров Сардинию, где вскоре и умер.

Едва окончилась война с Лепидом, как Помпею пришлось отправиться в Испанию. Здесь один из сторонников народной партии Серторий захватил ряд областей страны, угрожая войной Риму. Серторию удалось разбить одного за другим уже многих римских полководцев, посылаемых против него оптиматами. Теперь он воевал с Метеллом Пием - когда-то искусным полководцем и храбрым воином.