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

Когда война в Италии закончилась, бежавшие предводители марианцев стали готовиться к новым сражениям за морем, в Сицилии, Африке и Испании. Помпей, по предложению Суллы, взялся их уничтожить. Сначала он стал готовиться к походу на Кн. Карбона, который прибыл в Сицилию из Африки, но при известии о высадке неприятеля бежал на Коссиру, маленький остров между Сицилией и Африкой, Он был схвачен и в цепях привезен в Лилибеум. Здесь Помпей приказал умертвить его товарищей, даже не увидав их; напротив, Карбона, который некогда избавил его от преследований марианцев, человека, трижды бывшего консулом, молодой человек подверг формальному суду и, не тронутый его слезами и просьбами, холодно и торжественно произнес смертный приговор. За этот безжалостный суд современники жестоко порицали его; его называли мальчишкой-палачом (adolescentulus carnifex). Для военных подвигов в Сицилии не представлялось случая; он устроил дела на острове и с большим флотом из 120 военных и 800 транспортных кораблей переправился в Африку. Там он встретил войско Кн. Домиция Меднобородого (Ahenobarbus) в союзе с Парбом, царем нумидийским. Оба эти полководца со своими войсками были не в состоянии бороться с такой силой; Меднобородый пал после храброго сопротивления, Парб убежал, но скоро попал в руки Помпею и был казнен. Его царство отдано было родственнику его Гиемпсалу.

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