Pompeius katonai hírneve és alkalmankénti rossz megítélése tovább folytatódott, amikor proconsular imperiumi rangot követelt (bár még nem szolgált consulként), hogy Hispániába menjen [[Quintus Sertorius]], marianus hadvezér ellen harcolni. Egészen addig megtagadta legiójánaklégiójának feloszlatását, amíg a kérését nem teljesítették, és ekkor a kor egyik legsikeresebb hadvezéréhez, [[Quintus Caecilius Metellus Piushoz]] csatlakozott Sertorius ellen. A briliáns tehetségű hadvezér elleni hadjárat Kr. e. 76-tól Kr. e. 71-ig tartott. A háború végül akkor fejeződött be, amikor Sertoriust riválisai meggyilkolták, mivel Pompeiusnak vagy Mettelus Piusnak nem sikerült volna tiszta győzelmet aratnia a csatatéren.
A Sertorius halálát követő hónapokban Pompeius azonban felfedte egyik legjelentősebb tehetségét a meghódított tartomány kiváló irányításával. Pártfogását kiterjesztette egész Hispániára és dél Galliára. Amikor [[Marcus Licinius Crassus|Crassus]] nehézségekkel szembesült [[Spartacus (gladiátor)|Spartacussal]] szemben Kr. e. 71-ben, Pompeius visszatért Itáliába csapataival, hogy letörje a lázadást. Bár Crassus már majdnem teljesen leverte a felkelést és Pompeius csak a maradék lázadókat győzte le, a győzelmet neki tulajdonítják.
Az elégedetlen ellenzék, főleg Crassus, azt állítottákállította, hogy Pompeiusnak különös érzéke volt a csaták végén megjelenni és learatni a győzelmi babérokat. Ez az ellentét egyre jobban elmélyült Pompeius és Crassus között az elkövetkező évtized során. Visszatérve Rómába Pompeius a második diadalmenetét tartotta hispániai győzelmei tiszteletére. Csodálói a korszak legnagyobb hadvezérének tartották. Kr. e. 71-ben, 35 éves korában Pompeiust consullá[[consul]]lá választották a politikailag támogatására szoruló Crassussal együtt, a Kr.e. 70. évre. Mindez egy harmadik személy, Caius Iulius Caesar befolyására történt.
