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