После победы Суллы в Италии и «избрания» его пожизненным диктатором его уцелевшие и еще надеявшиеся на победу противники попытались укрепиться в провинциях. Серторий господствовал в Испании, а Карбон — на Сицилии, Сардинии и в Африке. Против Сертория Сулла направил Гая Анния Луска, а против Карбона — Помпея. Хотя официально Помпей не занимал никакой должности, сенат предоставил ему всю полноту власти. Помпей высадился на Сицилии. Претор этой провинции Марк Перперна, ранее признавший власть Карбона, сдался, но некоторые сицилийские города еще сопротивлялись. Помпею, однако, удалось завладеть Гимерой, особенно упорно не желавшей ему подчиниться, а затем и другими городами. Карбон, оставив в Африке Гнея Домиция Агенобарба, зятя Цинны, с флотом, сам переправился на остров Коссуру. Там он был разбит отрядом, посланным Помпеем. Сам Карбон был захвачен в плен и казнен по приказу Помпея. Оставшийся в Африке Агенобарб собрал новое войско и заключил союз с нумидийским царем Гиарбом. Чтобы ликвидировать новую угрозу, Помпей высадился в Африке. Часть армии Агенобарба перешла на его сторону, но у вражеского полководца еще оставалось довольно сильное войско, поддержанное нумидийцами. Вскоре две армии встретились лицом к лицу. В условиях начавшейся бури Агенобарб решил отступить, и тогда Помпей, воспользовавшись тем, что при отходе войско его противника смешало боевой порядок, напал на него. В жестокой битве погибла почти вся армия Агенобарба, включая самого полководца. Нумидийский царь попал в плен. Помпей лишил его царского ранга и передал нумидийский трон Гиемпсалу, которого незадолго до этого с помощью римлян изгнал из своей страны Гиарб. После этого Помпей захватил ряд городов, которые еще не желали ему подчиниться, а затем вторгся в Нумидию, чтобы реально посадить Гиемпсала на трон. Попытки нумидийцев сопротивляться войскам Помпея были сломлены.

Такие успехи двадцатичетырехлетнего Помпея встревожили Суллу, который побоялся, как бы на волне своих побед тот не попытался захватить власть. Поэтому он приказал ему вернуться в Рим с одним легионом, распустив остальное войско. Это вызвало недовольство солдат Помпея, которые даже попытались побудить своего командующего идти на Рим и свергнуть Суллу. Но Помпей на это не решился. Он остался верным Сулле и сумел убедить солдат подчиниться приказу диктатора. Известия о победах Помпея вызвали восторг в Риме. Противники Суллы к этому времени были полностью деморализованы сулланским террором, а его сторонники были готовы радостно приветствовать молодого полководца. Сулле пришлось смириться и сделать вид, что он тоже в восторге от Помпея и его побед. Он встретил Помпея за городом и объявил о присвоении ему прозвища «Великий» (Магн, Magnus), причем оно закреплялось по наследству. Но когда Помпей пожелал триумфа за свои победы в Нумидии (за победы над согражданами триумф отмечать было, естественно, нельзя), Сулла ему решительно отказал, ссылаясь на то, что он слишком молод и не занимал еще постов ни претора, ни консула. Лишь много позже, в 79 г. до н. э., под давлением солдат, любивших своего командира, которых поддержал и консул этого года Публий Сервилии Исаврик, который ранее Помпею противился, Сулла все же согласился, и Помпей справил пышный триумф, хотя еще даже не был сенатором.

Само согласие Суллы на триумф Помпея уже было в некоторой степени знаком начавшегося упадка его диктатуры. Недаром Помпей нашел смелость заявить, что больше людей поклоняется восходящему солнцу, чем заходящему, а затем против воли диктатора поддержал кандидатуру в консулы на 78 г. до н. э. Марка Эмилия Лепида. И если в 82 г. до н. э. Сулла убил своего верного сторонника Лукреция, поскольку тот решил стать консулом против его, Суллы, воли, то теперь помешать избранию Лепида он не смог. Сулле не было дано создать новый политический порядок; его диктатура выполняла скорее негативную роль разрушения старой республики. Да и сам Сулла, пожалуй, не подходил к роли создателя нового строя. Субъективно он был консерватором и стремился в первую очередь к восстановлению строя предков с всевластием сената и мизерной ролью демократических структур. Это противоречие субъективных стремлений и объективных результатов деятельности отразилось и наличной судьбе Суллы, который в том же 79 г. отказался от власти и официально превратился в частного человека, который в соответствии с законом готов ответить за все деяния во время диктатуры. Разумеется, никто не решился потребовать такого ответа. Сулла уехал в свое поместье и в следующем году умер.

Когда Сулла умер, Лепид решительно выступил против особых торжественных процессий и похорон за государственный счет. Против него выступил второй консул Квинт Лутаций Катул, которого активно поддержал Помпей. Положение в Риме накалялось. Лепид попытался объединить вокруг себя всех недовольных Суллой, в том числе бывших землевладельцев, потерявших земли в пользу сулланских ветеранов. В Этрурии вспыхнули волнения, и оба консула направились на их подавление. Но Лепид отвел свои войска к горам и не вмешивался в события, а Катул вернулся в Рим. После окончания своего консульства Лепид получил для управления Цизальпинскую Галлию, но не направился туда сам, а отправил в качестве своего легата Марка Юния Брута. Сам же, оставаясь в Этрурии, вскоре открыто выступил против римского правительства. В Риме началась паника. Катул далеко не был способным полководцем. И взоры римлян обратились к Помпею. Хотя официально во главе армии был поставлен как бывший консул Катул, фактически ее возглавил Помпей. Стремясь не допустить мятежника в Рим, Помпей занял Мульвийский мост через Тибр и холм Яникул. Здесь и произошла битва, в которой Помпей одержал победу. Лепид отступил в Этрурию, готовясь к продолжению борьбы, а Помпей, стремясь прежде всего изолировать его, направился в Цизальпинскую Галлию против Брута. Около города Мутины он разбил Брута. Сам Брут попал в плен, но вскоре был убит по приказу Помпея. Узнав о его поражении и не встретив активной поддержки в Риме, Лепид отступил и переправился на Сардинию, где и умер, а его преемник Марк Перперна отплыл еще дальше, в Испанию, где соединился с Серторием. Помпей с торжеством вернулся в Рим, и все прославляли его как спасителя государства.

Вернувшись в Рим, Помпей не стал распускать свою армию, а продолжал держать ее в лагере недалеко от города. А затем он потребовал, чтобы его направили в Испанию, где Серторий активно и успешно воевал против сулланских полководцев, в том числе против Метелла. Многие в Риме считали, что никто не сможет справиться с Серторием, кроме Помпея. Помпея активно поддержал Люций Марций Филипп. Именно он настоял в сенате, чтобы молодого человека, еще по возрасту не получившего доступа в сенат, не исполнявшего никакой общественной должности, отправили в Испанию в ранге проконсула. При этом Филипп не преминул, играя словами, насмешливо заметить, что Помпей посылается туда не только pro consule (вместо консула), но и pro consulibus (вместо консулов), намекая на полную неспособность обоих консулов 77 г. до н. э. возглавить подавление движения Сертория. Согласившись послать Помпея в Испанию, сенат, однако, ничего не сделал для реальной помощи ему в формировании армии. Правда, в его распоряжении было войско, с которым он разбил Брута, но этого войска было явно недостаточно для борьбы с Серторием. И Помпею снова, как шесть лет назад, пришлось набирать солдат за собственный счет. В течение сорока дней он собрал армию из 30 тысяч пехотинцев и 1000 всадников, с которой и выступил в поход.