В это время все большую роль в политической жизни Рима стал играть Гай Клодий, бывший в 58 г. до н. э. народным трибуном. Красноречивый демагог, яростный оратор, не останавливавшийся ни перед какими препятствиями, склонный решать вопросы в первую очередь прямым насилием, он стал любимцем толпы. Для достижения своих целей Клодий организовал не только группу политической поддержки, но и вооруженную шайку, которая все более терроризировала Рим. И он занял позицию, резко враждебную Помпею, возбуждая толпу против него, понося его, обвиняя в стремлении к тирании. Вопреки позиции Помпея, который стремился сохранить дружеские или по крайней мере доброжелательно-нейтральный отношения с Цицероном, Клодий добился изгнания Цицерона. Его сторонники открыто угрожали убить Помпея. Наглость Клодия дошла до того, что его подручные в мае 58 г. до н. э. похитили армянского царевича Тиграна и заключили его в доме трибуна, с тем чтобы затем переправить на Восток. Появление Тиграна младшего в Армении грозило разрушить весь тот порядок, который Помпей в результате своих побед создал в Восточном Средиземноморье и на Ближнем Востоке, и этого Помпей не мог не понимать. Более того, во время этого похищения был убит друг Помпея Папирий. И это переполнило чашу терпения Помпея.

До этого времени Помпей, искренне и глубоко влюбленный в свою молодую жену Юлию (ей было в это время, вероятно, 28 лет, и она была на 30 лет младше мужа), практически отошел от государственных дел и уединился с ней в своих загородных имениях. Но нападки Клодия заставили его вернуться к политической деятельности. Клодия считали «человеком Цезаря», и все видели за его бесчинствами руку галльского наместника. И это, конечно же, сказалось на отношении Помпея к своему союзнику по триумвирату. Чтобы противостоять Клодию и, как все считали, Цезарю, он сделал ставку на соперника Клодия Тита Анния Милона, которого стал всячески поддерживать. Но помимо этого Помпей счел необходимым пойти на сближение с сенатом, большинство которого только радовалось, видя то положение, в какое теперь попал Помпей, надеясь на его окончательную размолвку с Цезарем и, следовательно, на развал триумвирата. Некоторые из его друзей тоже советовали Помпею разорвать с Цезарем и даже развестись с Юлией, чтобы добиться союза с сенатом. Но Помпей не пошел на это. Сначала он вообще заперся в своем доме, а затем создал, по-видимому из своих ветеранов, вооруженный отряд, с которым отныне и появлялся на форуме и в других местах. В значительной степени с помощью этого отряда ему удалось одержать первую победу над Клодием: добиться возвращения Цицерона.

Несмотря на все нападки Клодия и недоброжелательство сенатского большинства, авторитет Помпея был довольно высок. И это показала история с хлебными беспорядками в сентябре 57 г. до н. э. Рим всегда зависел от провинций в доставке хлеба, а поставщики намеренно задерживали его отправку, чтобы поднять цены. И цены, действительно, резко возросли, а вскоре хлеба и вовсе стало не хватать, так что над городом нависла угроза голода. Этим воспользовался Клодий, который обвинил в нехватке хлеба Помпея и, как ни странно, Цицерона (впрочем, он всегда был готов всегда и во всем обвинять Цицерона), и по его призыву толпа устремилась на Капитолий с требованием хлеба. В ход были пущены камни. Консул Квинт Цецилий Метелл Непот, бывший легат Помпея и народный трибун, а теперь, как и все Метеллы, враг Помпея, был вынужден собрать сенат для обсуждения хлебного вопроса. Три дня беспрерывно проходило это обсуждение, а толпа все настойчивее требовала, чтобы дело было поручено Помпею. Все вспомнили, что десять лет назад при одном только его назначении вести войну с пиратами цена на хлеб сразу же понизилась. И Цицерон предложил начать по этому поводу переговоры с Помпеем. Несмотря на явное нежелание и консула, и сенатского большинства, с этим предложением пришлось согласиться. На следующий день Помпей явился в сенат и заявил о своем согласии при условии предоставления ему 15 легатов и чрезвычайных полномочий. Консулы согласились с этим и опять же по предложению Цицерона, который, будучи частным лицом, не имел права вносить закон от своего имени, сформулировали закон, который и был принят. По этому закону Помпею на пять лет вручалась верховная власть проконсульского ранга над всеми кораблями, перевозящими зерно, гаванями, торговыми центрами на всей территории Римской республики — одним словом, чрезвычайные полномочия по снабжению Рима хлебом, и в его подчинение назначались 15 легатов. Клодий выступил против этого закона, заявив, что сама нехватка хлеба была организована Помпеем для приобретения новой власти, но на этот раз он потерпел поражение, ибо слишком велика была надежда римлян на способность Помпея решить хлебную проблему. Трибун Гай Мессий предложил расширить его полномочия, предоставив ему также imperium maius, т. е. положение, при котором его власть в провинциях была выше власти наместников. Это предложение, по-видимому, не прошло. Но и так власть Помпея была огромна.

Помпей сразу же приступил к организации новой экспедиции. Он назначил легатов и, как когда-то при организации борьбы с пиратами, поручил им действовать одновременно в разных провинциях. Среди легатов были братья Цицероны. Квинта он направил на Сардинию, а знаменитый оратор Марк был оставлен в Риме в качестве связующего звена между Помпеем и столицей. Несмотря на наступление поздней осени, когда обычно всякое мореплавание прекращалось, Помпей отправился на Сицилию, а затем на Сардинию и в Африку. И он очень быстро добился своей цели: еще до нового года в Рим было доставлено столь большое количество хлеба, что цены на него сразу упали. Угроза голода была устранена. В январе 56 г. до н. э. Помпей еще находился вне Рима, продолжая выполнять поручение правительства, но уже довольно скоро возвратился в город и снова принял участие в политической жизни республики. Успешное решение хлебной проблемы снова сделало Помпея самым популярным человеком в Риме.

В конце 60-х и в первой половине 50-х гг. I в. до н. э. окончательно формируется «партия» Помпея. В начале своей карьеры Помпей сам примыкал к группировке Метеллов, но, как говорилось выше, его развод с Муцией привел и к разрыву с Метеллами. Но теперь вокруг него объединяются самые разные люди. Многие из них были земляками Помпея из Пицена и среди них был Люций Афраний. Будучи довольно низкого происхождения, он выбился наверх с помощью Помпея. В качестве легата Помпея он участвовал в войне с Серторием, а затем в том же качестве и в восточной кампании. Благодаря поддержке Помпея он даже стал в 60 г. до н. э. консулом. И в дальнейшем он не покидал своего патрона. Другим верным помпеянцем и тоже, вероятно, пиценцем был Авл Габиний. В 67 г. до н. э. он был народным трибуном и предложил закон о передаче Помпею верховного командования в войне с Митридатом. Позже он сам участвовал в этой войне как легат Помпея и многим помог своему командующему. При поддержке Помпея он был избран претором, а затем и консулом 58 г. до н. э., после чего был послан проконсулом Сирии.

К знатной и старинной римской фамилии принадлежал Марк Эмилий Скавр, который был квестором Помпея во время войны с Митридатом, а позже был оставлен Помпеем управлять только что образованной провинцией Сирией; в 58 г. до н. э. он был эдилом, в 56 г. претором, а затем управлял Сардинией. Соратником Помпея был Фауст Корнелий Сулла, сын диктатора. В армии Помпея он служил в должности военного трибуна, и именно он во время штурма Иерусалима первым ворвался в храм. Позже он занимал ряд должностей в Риме и был женат на дочери Помпея. После некоторых колебаний к Помпею примкнул известный ученый того времени Марк Теренций Варрон. Позже помпеянцем стал Люций Скрибоний Либон, на дочери которого Помпей женил своего младшего сына Секста. Во время консульства Цезаря против его аграрного закона, столь желанного Помпею, выступил Марк Петрей, но затем он изменил ориентацию и примкнул к Помпею, став его верным сподвижником. Петрей был старым солдатом и прославился в январе 62 г. до н. э., когда во время болезни (вероятнее всего, мнимой) консула Люция Антония возглавил армию, разгромившую мятежного Катилину. Столь же верным сподвижником Помпея был Марк Пупий Пизон, который рано выделился как оратор, а политическую карьеру начал еще в 83 г. до н. э., когда был квестором. Позже он был претором, успешно воевал в Испании, за что получил триумф, и все время, пока Помпей воевал сначала против пиратов, а затем на Востоке, служил его легатом, принимая участие во всех важнейших боевых действиях. Вернувшись в Рим, он стал в 61 г. до н. э. консулом и позже занимал видное место в группировке Помпея, выполняя в том числе его деликатные дипломатические поручения, как, например, переговоры с Клодием. Видное место среди соратников Помпея занимал Люций Лукцей, бывший одновременно и другом Цицерона. Ранее он был городским претором, наместником Сардинии, обвинял Катилину. В 60 г. до н. э. триумвиры выдвинули его кандидатуру на выборах консула на 59 г. в качестве коллеги Цезаря, но он потерпел поражение от Бибула. Лукцей попытался выступить и на научном поприще, желая написать исторические сочинения, в том числе и о борьбе с Каталиной, но, по-видимому, так и не исполнил свое намерение.