Когда война в Италии закончилась, бежавшие предводители марианцев стали готовиться к новым сражениям за морем, в Сицилии, Африке и Испании. Помпей, по предложению Суллы, взялся их уничтожить. Сначала он стал готовиться к походу на Кн. Карбона, который прибыл в Сицилию из Африки, но при известии о высадке неприятеля бежал на Коссиру, маленький остров между Сицилией и Африкой, Он был схвачен и в цепях привезен в Лилибеум. Здесь Помпей приказал умертвить его товарищей, даже не увидав их; напротив, Карбона, который некогда избавил его от преследований марианцев, человека, трижды бывшего консулом, молодой человек подверг формальному суду и, не тронутый его слезами и просьбами, холодно и торжественно произнес смертный приговор. За этот безжалостный суд современники жестоко порицали его; его называли мальчишкой-палачом (adolescentulus carnifex). Для военных подвигов в Сицилии не представлялось случая; он устроил дела на острове и с большим флотом из 120 военных и 800 транспортных кораблей переправился в Африку. Там он встретил войско Кн. Домиция Меднобородого (Ahenobarbus) в союзе с Парбом, царем нумидийским. Оба эти полководца со своими войсками были не в состоянии бороться с такой силой; Меднобородый пал после храброго сопротивления, Парб убежал, но скоро попал в руки Помпею и был казнен. Его царство отдано было родственнику его Гиемпсалу.
За несколько месяцев Помпей окончил поход; в упомянутом сражении он показал себя, как и всегда, храбрым, способным воином, сражаясь без шлема впереди своих солдат; но с таким войском, какое было в его распоряжении, Самый заурядный полководец мог бы так же хорошо исполнить свою задачу. Его победа вовсе не доказывала его военных талантов; но он все-таки имел притязания на отличие и славу; он помышлял о триумфе, в котором мог бы явиться с блеском как покоритель Африки. Ради этого он занялся охотой на львов и слонов, чтобы показаться в Риме с этими животными. Но в это время он неожиданно получил от Суллы приказ распустить свое войско, оставив только один легион, и ждать в Утике своего преемника; таким образом, ему пришлось возвратиться в Рим уже не полководцем, а частным человеком; его лучшие надежды были разбиты. Сам он не решался на открытое сопротивление; но войско, вероятно, по его побуждениям, воспротивилось приказу и, восстав против тирана Суллы, объявило, что оно не расстанется со своим полководцем. В Италии распространился слух об измене Помпея, и Сулла жаловался на свою судьбу, говоря, что ему на старости лет приходится сражаться с мальчишками – еще недавно он воевал с молодым Марием, теперь должен идти против Помпея. Но вскоре тот получил успокаивающее известие: оставить при себе армию. Таким образом, Помпей возвратился в Италию с войском и был встречен толпой народа как второй Александр; сам Сулла вышел ему навстречу, дружески протянул ему руку и громко поздравил его с титулом «Великий» (Magnus), перешедшим впоследствии и на его род. Но Помпей не удовлетворился этим лестным отличием; он требовал триумфа, вопреки закону и обычаю, так как триумф давался только тому, кто исполнял, прежде или теперь, высшие государственные должности; а Помпей не занимал еще никакой государственной должности, он был только помощником полководца, легатом диктатора Суллы. Но именно необыкновенное, чрезвычайное и привлекало тщеславного юношу, потому что этим доказывалось, что его подвиги были необыкновенны. Сулла противился его желанию, говоря, что у него еще не отросла борода, что он еще слишком молод для сенаторства, и если он, несмотря на то, вступит в город триумфатором, то это сделает ненавистным правление самого Суллы, а против Помпея возбудит всех граждан. Помпей не отступал и даже заметил Сулле, что восходящее солнце имеет больше почитателей, чем заходящее. Диктатор не побоялся такой угрозы «мальчика», но, досадуя на безграничную дерзость, воскликнул: «Ну пусть же будет ему триумф!» Этим закончились между ними все счеты. Таким образом, Помпей получил триумф и 80 г., двадцати шести лет от роду, как простой всадник, не будучи еще квестором. Чтобы сделать шествие более торжественным, он хотел въехать в город на четверке слонов; но, на его беду, ворота оказались слишком узкими, и он должен был довольствоваться простыми лошадьми. Солдаты также не с особенной радостью участвовали в триумфе. Им было досадно, что денежные подарки не соответствовали их ожиданиям, и потому они хотели при его вступлении в город поднять шум и испортить триумф; только тогда, когда он объявил им, что скорее откажется от триумфа, чем потерпит от них дерзость, они успокоились и смирно пошли за триумфальной колесницей.