Этот удар был особенно жестоким для Антистии, отец которой был убит за то, что поддерживал Помпея, а мать вскоре после развода дочери совершила самоубийство. Однако договорные браки являлись обычной частью политической жизни Рима, и от большинства бракосочетаний между аристократами женитьбу Помпея отличала только особая степень цинизма. Инициатива такого союза исходила от Суллы, но Помпей, кажется, довольно охотно выполнил его просьбу, желая угодить своему могущественному покровителю. Но брак оказался недолгим, ибо Эмилия вскоре умерла после рождения ребенка. Сенаторы редко оставались холостыми долгое время, и в 80 г. до н. э. Помпей женился на Муцие, происходившей из семьи знаменитого Муция Сцеволы. Таким образом Помпею удалось завязать еще одну полезную политическую связь.
Для сенаторов брак часто являлся вопросом политической целесообразности, а для пылкой страсти существовали любовницы, а не жены. Плутарх сообщает нам, что Помпей одно время поддерживал связь с куртизанкой Флорой, которая была настолько красива, что служила моделью для портрета, который Метелл Пий поместил в храме Кастора и Поллукса — подобная практика станет обычным явлением в эпоху Возрождения. Говорят, что Флора хвасталась страстной любовью к ней молодого полководца и демонстрировала следы его зубов после очередного свидания. Тем не менее Помпей даже в этом случае проявил честолюбие политика, который больше всего хотел, чтобы другие были ему обязаны, ибо в конечном счете он передал Флору своему другу, который также был влюблен в нее, но которому она отказала. Жертва Помпея выглядела еще значительнее, поскольку говорили, что он все еще влюблен в знаменитую красавицу.
Иногда поведение молодого Помпея больше походило на поведение эллинистического царевича, а не римского аристократа. Он слыл очень красивым, у него всегда была наготове отрепетированная улыбка, и он умел располагать к себе людей. Многие сравнивали его с молодым Александром, что, несомненно, льстило Помпею.
Хотя у него не было никакой официальной власти и он не входил в сенат, тем не менее Помпей обладал большим политическим влиянием. В 79 г. до н. э. он оказал поддержку в предвыборной кампании Марку Эмилию Лепиду. В результате должность консула на следующий год получил именно Лепид, а не ставленник Суллы. Такое оказалось возможным, поскольку Сулла уже сложил с себя звание диктатора и собирался перебраться в свое поместье в сельской местности. Его здоровье сильно ухудшилось, и жить ему оставалось всего несколько месяцев, хотя злые языки утверждали, что старик погряз в пороках. Лепид открыто заявил о своем намерении отменить многие законы Суллы, особенно ограничения, наложенные на власть народных трибунов.
Помпей не слишком хорошо разбирался в людях, а его уверенность в том, что он сможет контролировать поведение своих протеже, часто подводила его. Причины, по которым он поддержал Лепида, были неясны, но это решение оказалось серьезной ошибкой. Когда Сулла умер от неизвестной болезни (согласно подробным свидетельствам наших источников, его плоть гнила, а тело покрывалось язвами), Лепид попытался воспрепятствовать тому, чтобы Сулла удостоился общественной погребальной церемонии. Подобные похороны рассматривались сенаторами как большая честь. Помпей, то ли из давнишней привязанности к своему умершему покровителю, то ли из-за горьких воспоминаний о том, как обращались с телом его отца, был одним из тех, кто обеспечил надлежащие похороны. Прах Суллы был захоронен на Марсовом поле
Во время своего пребывания в должности консула Лепид возглавил открытый бунт армии против сената. Все отношения между ним и Помпеем были разорваны, поскольку Помпей не присоединился к мятежному консулу и охотно согласился на отчаянный призыв сената выступить против бунтовщика. Помпей быстро набрал несколько легионов (солдаты были основном из его родного Пицена, да и финансировал операцию большей частью сам Помпей).
После короткой кампании мятеж был подавлен. Помпей взял в плен и казнил старшего легата Лепида Марка Юния Брута (отца человека, который возглавит заговор против Цезаря в 44 г. до н. э.). Лепид бежал на Сардинию, где впал в отчаяние и вскоре умер. Говорили, что он был больше подавлен не неудачей с мятежом, а тем, что обнаружил неверность своей жены. Многие мятежники, включая Перперну, отправились в Испанию и, в конечном счете, присоединялись к Серторию.