キンナは紀元前84年、アンコーナで起こった暴動によって死んだが、ポンペイウスもこのときアンコーナにいたと考えられており、スッラ側かと疑われたためピケヌムに引き払った[14]。
スッラの帰還と栄誉

紀元前83年、ミトリダテス戦争に勝利したスッラは、マリウスやキンナ亡き後のローマを制圧するためにギリシアから軍を率いて戻ってきた。ポンペイウスはピケヌムのキンナ派有力者を追放し、自費で募兵した3個軍団を率いてスッラの軍へ合流した。スッラはポンペイウスの参戦が、キンナ派のプロコンスル、グナエウス・パピリウス・カルボ有するローマ軍団への対応に有用であったこともあり、ポンペイウスの合流を歓迎したという。紀元前82年、スッラがローマ市を制圧してプロスクリプティオに基づく密告を導入してポプラレスの多くを殺害した。スッラは独裁官（ディクタトル）となった後、ポンペイウスを繋ぎ止めるため、アンティスティアと離婚して、スッラの4人目の妻カエキリア・メテッラとその元夫マルクス・アエミリウス・スカウルスの間の娘アエミリア（Aemilia Scaura）と結婚するよう強要し、ポンペイウスは従わざるを得なかった[15]。

スッラはイタリア本国が落ち着いたところで、シキリア属州やアフリカ属州へ逃れて未だ残るポプラレスの征討をポンペイウスに命じたが、紀元前82年の内にシキリアはあっさりとポンペイウスの手に落ち（シキリアは当時のローマにとって重要な穀倉であり生命線であった）、カルボ及びポプラレスを多数捕らえて殺害した。紀元前81年にはヌミディアへ逃れていたグナエウス・ドミティウス・アヘノバルブス（ルキウス・ドミティウス・アヘノバルブスの兄）を殺害、ドミティウスに組したヒアルバスを捕虜としてヒエムプサル2世（ユバ1世の父）をヌミディア王に据えた。[16]

これらの功績を以て、ポンペイウスは「インペラトル」と呼ばれ、スッラからは「マグヌス」と評された（ポンペイウスはスッラ生存中は「マグヌス」と名乗ることはなく、スッラ死去後に使うこととなる）。ポンペイウスはシキリア・アフリカでの勝利を以て凱旋式を挙行できるようにスッラに申し出て、難色を示したスッラに対して強気な姿勢を示して認めさせた。25歳での凱旋式はスキピオ・アフリカヌスを上回る最年少記録であった[17]。紀元前78年にスッラが死亡した時、ポンペイウスはクィントゥス・ルタティウス・カトゥルスらと共にスッラの国葬を主張し、軍隊の支持もあってこれが認められた[18]。
ヒスパニア遠征ヒスパニア

紀元前77年、ガリア・キサルピナ属州総督として赴任する予定であったマルクス・アエミリウス・レピドゥスが中部イタリアで反スッラを掲げて挙兵した。ポンペイウスは執政官カトゥルスの代理としてレピドゥス討伐に赴き、レピドゥスを敗死させた。しかし、レピドゥス軍の残党はヒスパニアで反乱を起していたポプラレスのクィントゥス・セルトリウスに合流したことで、セルトリウス軍は勢力を拡大した。セルトリウス戦争（英語版）にはクィントゥス・カエキリウス・メテッルス・ピウスが当っていたが、ポンペイウスはメテッルス・ピウスに代わって、セルトリウス討伐軍の指揮に名乗りを挙げた。

元老院はポンペイウスが軍事面での才能が抜群であることは認めながらも、29歳と若くコンスルやプラエトルの経験が無いこと（共に任期後は属州を担当する権限が与えられる高位政務官）やメテッルス・ピウスの指揮が決して悪くは無かったことから、ポンペイウスへ指揮権（インペリウム）を付与することに躊躇したものの、ポンペイウスが手持のローマ軍団を解散するのを拒否したことやポントス王ミトリダテス6世が蠢動し始めたこともあって、ポンペイウスへ指揮権を与えて、ヒスパニアへ派遣することを元老院は決議した。

ポンペイウスはヒスパニアまでの補給線を確保するべく、ローマからヒスパニアまでの街道を構築しながらの行軍となったため、ヒスパニア到着は翌年の紀元前76年となった。メテッルス・ピウスが人格者であったこともあり、ポンペイウスとの関係に齟齬が生じることもなく、ローマ軍の指揮系統が乱れることはなかった。セルトリウスは狭隘なヒスパニアの地形を駆使したゲリラ戦を展開してローマ軍を苦しめたが、物量に勝るローマ軍に対峙して、先の見通しが立たなくなりつつあったセルトリウス軍は内部分裂を起し、4年後の紀元前72年にセルトリウスは配下の将軍マルクス・ペルペルナによって殺害された。これによって反乱軍は弱体化してこの年の内に反乱は鎮圧された。

ポンペイウスは私財を投げ打ってヒスパニアで戦っており、紀元前74年には元老院に対して戦費を要求した。もし要求が通らなければ、スペインを見捨てて軍団と共にイタリアへ戻ると宣言したため、ミトリダテス戦争のインペリウムを狙っていた当時の執政官ルキウス・リキニウス・ルクッルス（メテッルス・ピウスの従兄弟）は、なんとしてでもこの要求を認めさせ資金を送ったという[19][20]。
執政官就任

セルトリウスの反乱が鎮圧されてから数カ月間、ポンペイウスはヒスパニアの統治体制再構築に乗り出して、ポンペイウスの施策が公平であったこともあり、ヒスパニア住民から高い支持を得ることとなった。これにより、ヒスパニアはポンペイウスの有力な勢力圏の一つになった。

ポンペイウスがヒスパニアで戦っていた最中の紀元前74年、第三次奴隷戦争が勃発しルキウス・ゲッリウス・プブリコラらが鎮圧に当ったものの、奴隷側の首謀者であったスパルタクスの巧みな用兵もあって長期化していた。紀元前71年、スッラの部将だったマルクス・リキニウス・クラッススがルカニアでスパルタクスを討ち取って反乱軍は壊滅状態となったが、ポンペイウスはこの時に軍を率いてガリアなど北部へ逃亡を図った反乱軍の残党を粉砕した。ポンペイウスはクラッススに先んじて元老院へ「この戦いを終わらせたのは私である」と報告し、ローマ市民もこれを認めた[21]。これによって第三次奴隷戦争での武勲を横取りされた格好となったクラッススは、ポンペイウスの高い人気への嫉妬も重なって激しい敵愾心を持つこととなった。

ともかく、セルトリウスの反乱及び第三次奴隷戦争での武勲によって、ローマ市民から絶大な支持を獲得したポンペイウスは紀元前71年にコンスル（43歳以上にのみ就任資格がある）への立候補及び凱旋式挙行等を認めることを元老院へ要求。また、ルビコン川まで到達したにもかかわらず、軍団を解散せず、保持し続けることで圧力を掛けた。元老院議員の資格すら持たないポンペイウスのこの要求に元老院は難色を示したものの、ポンペイウスに対抗する力を持つクラッススがポンペイウスへの嫉妬から自らもコンスルへ立候補する意志を表明したことで、元老院の思惑は外れることとなった。この際にクラッススとポンペイウスの間で協定が結ばれたともされ、紀元前70年にポンペイウスは選挙で圧倒的な支持を受けて、クラッススと共に35歳でコンスルに選出された。

執政官就任時期に、プラエトルであったルキウス・アウレリウス・コッタが起草した、裁判陪審員を元老院議員、エクィテス、恐らくトリブスの有力者であるトリブニ・アエラリイの3階級から同数選出する「アウレリウス法」が可決され、スッラのコルネリウス法で縮小されていた護民官の拒否権などの権限を戻すことも決定した。