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