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