Гиртулей разбил Кальвина. И после этой победы значительная часть испанских племен уже на территории Ближней Испании присоединилась к Серторию. Часть испанцев, как и лузитаны, признали его своим верховным вождем, а кельтиберы объявили его своим патроном, а себя его клиентами. Значительная часть испанцев «посвятила» себя Серторию: они дали клятву умереть вместе с ним, шли за ним, не раздумывая, и с риском для жизни спасали его в случае необходимости. Это был древний кельтский обычай, засвидетельствованный не только в Испании, но и в Галлии. В глазах кельтиберов Серторий выступал наследником их старой родовой аристократии. Они питали почти мистическую веру в этого человека и видели знак особого покровительства ему сверхъестественных сил в белой лани, которая всюду его сопровождала, ибо культ оленя был широко распространен на Пиренейском полуострове.
Победы Сертория привлекали к нему все большее число испанцев. Суллу встревожило положение в Испании. На место Фуфидия он послал Квинта Цецилия Метелла Пия. Мы уже встречались с ним в рассказе о Ливии Друзе. Он был сыном полководца, сражавшегося против Югурты, и упорного врага Мария. И сам Метелл уже прославился и на военном, и на гражданском поприще. Он был претором в 89 г. до н. э. и пропретором, принимал активное участие в гражданской войне на стороне Суллы, одержав ряд важных побед, а в 80 г. до н. э. был консулом вместе с самим Суллой, который ему безгранично доверял. В следующем году Сулла сделал его проконсулом Дальней Испании, отправив вместе с ним значительную армию, состоявшую из двух легионов и большого количества вспомогательных частей. Главной задачей Метелла была война с Серторием.
Метелл был более опытным и известным полководцем, чем Кальвин, и он фактически взял на себя руководство военными операциями на Пиренейском полуострове. Метелл разработал план одновременного удара по Серторию действиями своего войска и войска Кальвина: они должны были взять армию Сертория в тиски и раздавить ее в них. Но Серторий, предвидя действия сулланских наместников и понимая всю их опасность, опередил противников. Он снова направил Гиртулея против Кальвина, а сам обрушился на Метелла. И тут, и там были одержаны победы. План Метелла провалился. Теперь он действовал без спешки. Главной задачей Метелл считал установление контроля над важнейшими дорогами и овладение некоторыми городами. С этой целью был основан ряд римских лагерей и городков. Серторий тоже не решался на окончательное сражение и ограничился неожиданными рейдами и разгромом отдельных частей противника. Метелл обратился за помощью к наместнику Трансальпийской Галлии Люцию Манлию, но его войска были встречены в Пиренеях частями Гиртулея и разбиты. Серторий сумел установить хорошие отношения с аквитанами, живущими по ту сторону Пиренеев, и угроза с их стороны окончательно парализовала Манлия, так что о помощи Метеллу и Кальвину не могло быть и речи. Война затягивалась.
В 79 г. до н. э. Сулла неожиданно отказался от власти, а в следующем году умер. Но у власти в Риме остались его сторонники, так что Серторий не имел основания прекращать борьбу. Но вскоре в среде сулланцев обнаружились противники существующего режима. Бывший активный сторонник Суллы Марк Эмилий Лепид поднял восстание с целью восстановления досулланского положения, но был разбит под стенами Рима. Остатки его армии переправились на Сардинию, где Лепид умер, а во главе отряда встал Марк Перперна. Перезимовав на Сардинии, Перперна решил отправиться в Испанию и присоединиться к Серторию. 20 тысяч пехотинцев и 1500 всадников под командованием Перперны высадилось на Пиренейском полуострове. Перперна попытался самостоятельно воевать с Метеллом, но неудачно, а его воины все настойчивее требовали объединить все силы и сделать общим командующим Сертория, слава которого уже гремела не только в Испании, но и в Италии. По происхождению Перперна был гораздо знатнее Сертория и отличался повышенным самомнением, но в конце концов ему пришлось уступить. Обе армии объединились, и Серторий встал во главе всех антисулланских сил в Испании. Это усилило повстанцев, хотя и сделало их силы более разнородными.