Объединив под своим командованием значительные силы, состоявшие и из римских эмигрантов, и из аборигенов, Серторий развернул военные действия. Гиртулей наголову разбил войска Кальвина, и Кальвин погиб в сражении, а сам Серторий с успехом сдерживал Метелла. Положение было столь грозным, что в Риме решили принять чрезвычайные меры. Было решено направить в Испанию еще молодого, но уже прославившегося Гнея Помпея. Он еще не занимал никаких общественных должностей и даже не был сенатором, но тем не менее его возвели в ранг проконсула. В этом качестве он довольно быстро собрал новую армию и в конце 77 г. до н. э. появился на Пиренейском полуострове. С этого времени именно Помпей стал главным врагом Сертория.
Серторий стремился создать единый фронт борьбы с сулланским режимом. Исходя из правила, что враг моего врага — мой друг, он пошел на переговоры с понтийским царем Митридатом. Разбитый Суллой, Митридат не отказался от своих попыток создать мощную державу, спорящую с Римом за власть на Востоке, и попытался воспользоваться гражданской войной в Италии для возобновления войны. Он был быстро разбит, и мирный договор восстановил довоенное положение. Теперь Митридат подготовился тщательнее и решил вступить в переговоры с Серторием. Непосредственными инициаторами переговоров стали два римских эмигранта Магий и Фанний, находившиеся при дворе Митридата. В свое время они были воинами в армии Гая Флавия Фимбрии, которая была направлена против Митридата антисулланским правительством. Фимбрия сумел одержать ряд побед, но Сулла, торопившийся развязать себе руки для борьбы в Италии, заключил с Митридатом мир, а затем сумел переманить на свою сторону большинство солдат Фимбрии. Вскоре после этого сам Фимбрия покончил с собой, а часть его воинов, не желавших перейти на сторону Суллы, перебежала к Митридату, надеясь, видимо, с его помощью свергнуть сначала диктатора, а затем его преемников. Среди них и были Магий и Фанний, которые решили объединить все антисулланские силы, т. е. Сертория на Западе и Митридата на Востоке. В таких условиях они становились участниками продолжающейся гражданской войны, а не прислужниками чужого царя. Митридат легко согласился с инициативой и направил их своими послами к Серторию, который и ввел послов в сенат, а затем настоял на заключении договора с понтийским царем. Заключая договор, Серторий явно действовал как преемник и в настоящее время глава законного правительства республики, находившегося в изгнании в Испании.
По условиям договора, Серторий соглашался признать за Митридатом Каппадокию и Вифинию в Малой Азии, которые, хотя и находились под сильным римским влиянием, официально были независимыми царствами. За это Митридат давал Серторию 40 кораблей и 3 тысячи талантов денег. Объединение врагов создавало огромную угрозу для римского правительства. Возможно, что какие-то известия о предполагаемом союзе послужили решающим аргументом для отправления в Испанию Помпея с новым войском. Одновременно правительство развернуло широкую пропагандистскую кампанию для дискредитации Сертория. В ход была пущена версия, согласно которой Серторий якобы отдавал Митридату не только Каппадокию и Вифинию, но и римскую провинцию Азию. Сенат, по-видимому, объявил его врагом римского народа, что официально ставило его вне закона. Воспользовавшись тем, что значительная часть войска Сертория состояла из испанцев, сенат счел войну с ним не гражданской, а «внешней». Это значило, что все, кто хотя бы сочувствовал Серторию, становились предателями родины.
Однако полностью убедить римское общественное мнение эта пропаганда не смогла. Значительная часть плебса ждала Сертория. Благожелательно относились к нему средние слои римского населения и муниципальная аристократия, т. е. верхушка италийских городов, получивших после Союзнической войны полное римское гражданство. В каких-то связях с мятежным вождем находилась и часть собственно римской знати, оппозиционная к существующему режиму. Все эти круги населения видели в Сертории не мятежника, а единственного еще активно действующего вождя антисулланской «партии», использующего Митридата, пиратов, испанцев как орудия в борьбе с сулланским сенатом. Но все же сила инерции, заданной сулланским террором, была еще столь сильна, что оказать какую-либо реальную помощь Серторию его сторонники в Риме и Италии не могли. Дело решалось на полях сражений в Испании.