公元前7 0 年，庞培如愿当选执政官，同时当选的是克拉苏。这本身就违反了苏拉制定的法律（庞培的年龄还不到竞选执政官的 40 岁下限）。但罗马元老院最后还是屈服了----原因很简单，庞培手里有一支忠诚于自己的军队，而苏拉尽管赋予元老院极大的权力，唯独忘记给它留下一支军队，一旦胜利的将军用武力胁迫元老院时，它便显得无能为力了。
庞培和克拉苏当选执政官之后发现，苏拉独裁的“后遗症”接踵而来，罗马的政治局势变得动荡不安。为了获取民众的赞誉，也为了缓和矛盾，新上任的执政官立即集中精力推翻苏拉所建立的制度。苏拉当年恢复了元老院的权力，庞培就反其道行之，尽力打击元老院。庞培还提出了一项废除苏拉所强加于保民官职务的一切限制的法案，恢复保民官的原有权力。
在经济上，被苏拉取消的包税制也在东方行省得到了恢复（这符合克拉苏所代表的富裕骑士的利益）。总之一句话，曾经作为苏拉的坚决追随者的庞培和克拉苏，反而做到了反对派在苏拉独裁后一直想做而一直没能做到的事。就这样，苏拉恢复传统秩序的全部努力几乎都被否定了，罗马政治重新回到往日的反复多变和混乱无序的状态。
海盗克星
但庞培本人却是这一新体制的受益者。公元前 70 年执政官任期届满后，庞培暂时退出了政治舞台。但他当然不会像其他退位的执政官一样，安分守己地安居幕后，不再期待得到更多的荣誉和权力。不过 3 年之后的公元前 7 年，正是一位保民官向公民大会提议，推选一位统帅，赴地中海海域清剿海盗。
地中海海盗问题可以说是由来已久。地中海基本是个内海，内海的特点是风向多变，加之周边地形复杂，形成许多海湾，给那些以袭击抢劫货船为生的海盗提供了方便条件。公元前 2 世纪以来，海盗一直在地中海肆无忌惮地横行。他们利用自己的船只、武装和罗马的贵族骑士串通一气，袭击来往商船，抢劫沿海城市，从事贩卖人口的勾当。
以此看来，海盗已经到了不杀不足以平民愤的地步，那位保民官的提议恰是时候。尽管其中没有直接提到庞培的名字，但若法令得以通过，以军功著称的庞培势必成为呼声最高的人选。或许这正是庞培自己在背后秘密筹划出来的行动也未可知。不仅如此，这位保民官进一步提出，授权统帅在离岸 90 公里以外的地中海拥有最高指挥权（为期 3 年），负责查禁海盗，并给他配备 12 万步兵与 5000 骑兵（相当于 20 个军团），以及 270 艘战船，并授权他在需要时任意扩充军队。
在此之前的罗马历史上，还从来没有哪一个统帅获得过如此大的军事、行政权力。这不啻让这位统帅变为一个凌驾于共和国之上的君王：无论在陆地还是在海上，都由他一个人说了算，可以无视罗马行政长官的任何决议，因此，元老院并不是没有人提出反对，但微弱的反对声无法阻止公民大会压倒多数通过了对庞培的任命。
庞培本人也胸有成竹。庞培面对地中海海域辽阔而海盗神出鬼没的情况，制定出分片包抄战术。一方面，他下令封锁全部海岸线数十里以内的地区，派步兵日夜巡逻，以断绝给海盗的给养；另一方面，他又将地中海以及自己的军队和武器装备划为13部分，分别交与副将指挥，在地中海上撒下罗网，形成处处有军队与海盗交战的态势。
他以闪电般的快速行动打了海盗一个指手不及，只用了 40 天，就扫清了西地中海的海盗。这一年即公元前 67 年的初夏，意大利的小麦进口就恢复到原本的数量。随后，庞培又挥师转战爱琴海，仅用 7 周时间，就消灭了奇里乞亚海的海盗。只用了短短 3 个月时间，庞培就出色地完成了平定海盗的任务。
比起庞培取得的军事成就，更令人震惊的是他对待俘虏仁慈宽容的态度。此前，罗马人对俘获的海盗一般均判处死刑，但庞培并不是个头脑简单的赳赳武夫。他在清剿海盗的过程中，对那些愿意归降的海盗进行了妥善的处置，让他们享有自由的身份，并在小亚细亚和希腊的一些地区分给他们一小块土地，安居下来。这种怀柔政策瓦解了海盗内部的势力，使这场清剿战争能在极短的时间内顺利结束，从根本上清除了海盗势力重新抬头的隐患。