幸存的马里安派（marians）逃往西西里，他们的盟友马库斯·佩尔佩尔纳（marcus perperna）担任该地的执政官。
他们得到了卡尔波（carbo）指挥的舰队的支持，而盖乌斯·多米提乌斯·阿亨巴尔布斯（Gnaeus domitius Ahenobarbus）则占领了罗马的非洲省。
庞培的大军登陆西西里后，佩尔佩尔纳放弃了该岛，而卡尔波则被捕并随后被处决。
庞培声称这是因为卡尔波对罗马公民的犯罪行为所致，但他的对手给他起了个绰号“年轻屠夫”（adulescentulus carnifex），以此来讽刺他。
庞培随后驶向非洲，将西西里留给他的妹夫盖乌斯·梅密乌斯（Gaius memmius）管理。
在尤提卡战役（battle of Utica）中，庞培击败并杀死了阿亨巴尔布斯，征服了努米底亚，并处决了与马里安派结盟的国王希阿尔巴斯（hiarbas）。
他恢复了被废黜的希普萨尔（hiempsal）回到努米底亚王位。
此时，庞培的部队开始称他为“伟大”（magnus），这个称号源于古希腊的亚历山大大帝（Alexander the Great），在罗马人中备受敬仰。
不久之后，庞培正式将其作为自己名字的一部分。
返回罗马后，庞培请求举办凯旋仪式以庆祝他的胜利，这对一个如此年轻的人来说是个前所未有的要求。
庞培拒绝解散军队，直到苏拉同意，尽管后者试图通过同时授予卢修斯·利基尼乌斯·穆雷纳（Lucius Licinius murena）和盖乌斯·瓦莱里乌斯·弗拉库斯（Gaius Valerius Flaccus）凯旋来减少影响。
在这段时间，庞培与强大的梅特尔斯家族成员穆基亚·特尔提亚（mucia tertia）结婚。
他们在公元前61年离婚之前育有三个孩子：通常被称为盖奈乌斯（Gnaeus）的庞培之子（pompey the younger）、女儿庞培亚·玛格娜（pompeia magna）和小儿子塞克斯图斯（Sextus）。
庞培支持马库斯·艾米利乌斯·莱比杜斯（marcus Aemilius Lepidus）担任公元前78年的执政官。
公元前78年，苏拉去世，莱比杜斯试图阻止他的国葬，并废除苏拉的一些法律，随后于公元前77年1月成为西高卢（cisalpine Gaul）和东高卢（transalpine Gaul）的前执政官。
当元老院命令他返回罗马时，莱比杜斯拒绝服从，除非被授予另一个执政官任期，这个提议迅速被拒绝。
莱比杜斯集结了一支军队，开始向罗马进军。
元老院随即采取了一系列措施，其中之一是任命庞培为军事指挥官。
在莱比杜斯继续向南推进时，庞培从他的退伍军人中募集军队，向北进军围攻西高卢的首府穆蒂纳（mutina）。
该城被莱比杜斯的盟友马库斯·朱尼乌斯·布鲁图斯（marcus Junius brutus）占据，布鲁图斯在经过长时间围城后投降，次日被暗杀， 据说是庞培的命令。
卡图卢斯（catulus）随后在罗马城外击败了莱比杜斯，而庞培则从后方进军，在科萨（cosa）附近捕获了他。
莱比杜斯和他残余的军队撤退到撒丁岛，并在那里去世。
---
塞尔托里战争（Sertorian war）始于公元前80年，当时着名的被迫害的马略派将领昆图斯·塞尔托里乌斯（quintus Sertorius）在伊比利亚（hispania）发起叛乱，加入了其他罗马流亡者，如佩尔珀尔纳（perperna）。
在当地伊比利亚部落的支持下，他控制了伊比利亚后省（hispania Ulterior），并通过巧妙的游击战术多次击败昆图斯·凯凯利乌斯·梅特鲁斯·皮乌斯（quintus caecilius metellus pius）。
塞尔托里乌斯击败了其他被派去驱逐他的罗马将领，并迅速征服了伊比利亚前省（hispania citerior）。
在参议院的支持下，庞培被任命为西班牙的军事指挥官，授予他执政官的权力以打败塞尔托里乌斯。
这一行为在技术上是非法的，因为他尚未担任公职，这突显了庞培对军事荣耀的偏好，以及对传统政治限制的蔑视。
庞培招募了3万步兵和1千骑兵，这证明了塞尔托里乌斯所带来的威胁严重性。
途中，他平息了加尔利亚·纳博讷（Gallia Narbonensis）的一场叛乱，之后他的军队在纳尔博·马尔提乌斯（Narbo martius）附近进入冬季驻扎。
公元前76年初，他越过了波尔特（col de portet），进入了伊比利亚半岛，并在那里停留了五年。
庞培的到来提振了梅特鲁斯部队的士气，部分叛军也转而投靠，但不久后他在劳龙战役（battle of Lauron）中被塞尔托里乌斯击败，损失了三分之一的军队，而对塞尔托里乌斯的军队几乎没有造成损失。
这对庞培的声望是一次严重打击，他花了剩余的一年时间重组自己的军队。
梅特鲁斯未能驱逐塞尔托里乌斯，而庞培的失败使得参议院的将领们在这一年没有取得任何进展。
公元前75年，塞尔托里乌斯对梅特鲁斯发起进攻，而庞培则在瓦伦西亚（Valencia）外击败了他的部下佩尔珀尔纳和盖乌斯·赫伦尼乌斯（Gaius herennius）。
当塞尔托里乌斯接管对抗庞培的行动时，梅特鲁斯在伊塔利卡战役（battle of Italica）中击败了他的副手卢修斯·希图列乌斯（Lucius hirtuleius）。
庞培与塞尔托里乌斯在不分胜负的苏克罗战役（battle of Sucro）中交战，塞尔托里乌斯击败了庞培的右翼，几乎抓住了庞培本人，但庞培的军团长卢修斯·阿弗拉纽斯（Lucius Afranius）击败了塞尔托里乌斯的右翼。
塞尔托里乌斯撤退到内陆，然后转向在萨古图姆（Saguntum）作战，庞培在此战中损失了6000人，包括他的妹夫梅米乌斯（memmius），他被誉为最有效的副手。
塞尔托里乌斯则损失了3000人，其中一人是希图列乌斯。
尽管梅特鲁斯在一场单独的战役中击败了佩尔珀尔纳，塞尔托里乌斯还是能在年底撤退到克鲁尼亚（clunia），在那里修复城墙以诱使对手围攻，并将其他城镇的驻军组成新的野战军。
一旦准备就绪，他就从克鲁尼亚逃脱，并用它来破坏罗马的陆路和海上后勤。
缺乏补给迫使梅特鲁斯的军队在高卢（Gaul）驻扎，而庞培则在瓦卡伊（Vaccaei）之间过冬。
由于这段战役造成的困境和塞尔托里乌斯的游击战，庞培不得不写信给参议院，请求资金和士兵，并指责他们对他和梅特鲁斯的缺乏支持。
庞培的信函有效地激励了参议院向他发送更多的士兵和资金。
公元前74年，他和梅特鲁斯开始对敌人发起消耗战，因为他的主要对手失去了大部分罗马军团士兵，无法在战场上与他匹敌，庞培与梅特鲁斯联手逐渐占据优势，征服越来越多的塞尔托里乌斯城市，缓慢地磨灭了塞尔托里乌斯的叛乱。
此时，塞尔托里乌斯也遭到内部分歧的削弱。
公元前72或73年，塞尔托里乌斯的伊比利亚和罗马联军内部的不满达到顶峰，佩尔珀尔纳在其他着名的塞尔托里乌斯派人士的带领下策划阴谋，刺杀了塞尔托里乌斯，并接管了叛军。
庞培与佩尔珀尔纳交战，并在奥斯卡（osca）附近的战役中迅速击败了他。
佩尔珀尔纳被捕，试图说服庞培饶恕他，交出塞尔托里乌斯的信件，信中包含了塞尔托里乌斯与罗马主要人物的通信证据。
庞培未读信件便将其烧毁，并处决了佩尔珀尔纳，随后花了一段时间重组当地的罗马行政，表现出对昔日对手的宽容，这使他在伊比利亚和南高卢的影响力得以延续。
庞培和他的军队在伊比利亚停留了几年，征服塞尔托里乌斯残余势力，随后回到罗马。