Сначала Помпею пришлось иметь дело с альпийскими племенами, преграждавшими путь его армии. Хотя южная часть Галлии была уже довольно давно подчинена Риму и образовывала римскую провинцию Трансальпийскую Галлию (Галлию поту сторону Альп), альпийские горные племена оставались еще независимыми и постоянно угрожали связям Италии с этой провинцией. Помпей сумел не только их разбить и освободить себе путь, но и отбросить их в Галлию и даже в Испанию. При этом его воины проложили новую и более удобную дорогу из Италии в Галлию. После этой победы армия Помпея оказалась в Трансальпийской Галлии. Но и там поход помпеевских воинов не был легкой прогулкой. Часть местных племен отказалась подчиняться и Риму, и греческому городу Массалии, союзному с Римом. Помпею пришлось с оружием в руках снова подчинять эти племена. И только после этих побед он сумел пройти к Пиренеям, через которые он стал с боем прорываться в Испанию. В честь своих побед в этих горах он воздвиг там свой триумфальный памятник, который и позже был известен как Трофей Помпея.

Главной задачей Помпея было укрепление на средиземноморском побережье, куда он пробился в конце 77 г. до н. э. Хотя большинство приморских городов, как уже говорилось, к Серторию не примкнуло, утвердиться на побережье Помпей смог далеко не сразу и не без труда. Серторианская армия под командованием Перперны была вынуждена отступить, но в дело вмешался Серторий со своими основными силами. Помпей задумал начать наступление на Сертория с двух сторон. Для этого он направил часть своей армии во главе с Гаем Меммием против Перперны, засевшего в Валенции, а сам с главной частью войска двинулся против Сертория. Но в сражении около Лаврона Помпей потерпел страшное поражение и был вынужден отступить за реку Ибер. После этого Серторий окружил Меммия в Валенции и заставил его оттуда уйти. Поражение серториевского полководца Гиртулея от Метелла, как уже говорилось в биографии Сертория, развязало руки Метеллу, и добить Помпея Серторий не смог. Чтобы удержать в своих руках побережье и лишить врага его баз внутри Испании, Помпей весной двинулся во внутренние районы страны, где захватил ряд городов. Еще одним успехом Помпея стал разгром армии Гиртулея и убийство ее полководца. После этого Помпей вернулся на побережье, где потерпел новое поражение от Сертория и был спасен только подошедшим войском Метелла. Объединение сил Помпея и Метелла создало перевес в силах, но в очередном сражении Помпей вновь был разбит, и лишь победа Метелла над Перперной позволила правительственным полководцам сохранить свободу действий.

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

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

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

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