Гиртулей разбил Кальвина. И после этой победы значительная часть испанских племен уже на территории Ближней Испании присоединилась к Серторию. Часть испанцев, как и лузитаны, признали его своим верховным вождем, а кельтиберы объявили его своим патроном, а себя его клиентами. Значительная часть испанцев «посвятила» себя Серторию: они дали клятву умереть вместе с ним, шли за ним, не раздумывая, и с риском для жизни спасали его в случае необходимости. Это был древний кельтский обычай, засвидетельствованный не только в Испании, но и в Галлии. В глазах кельтиберов Серторий выступал наследником их старой родовой аристократии. Они питали почти мистическую веру в этого человека и видели знак особого покровительства ему сверхъестественных сил в белой лани, которая всюду его сопровождала, ибо культ оленя был широко распространен на Пиренейском полуострове.

Победы Сертория привлекали к нему все большее число испанцев. Суллу встревожило положение в Испании. На место Фуфидия он послал Квинта Цецилия Метелла Пия. Мы уже встречались с ним в рассказе о Ливии Друзе. Он был сыном полководца, сражавшегося против Югурты, и упорного врага Мария. И сам Метелл уже прославился и на военном, и на гражданском поприще. Он был претором в 89 г. до н. э. и пропретором, принимал активное участие в гражданской войне на стороне Суллы, одержав ряд важных побед, а в 80 г. до н. э. был консулом вместе с самим Суллой, который ему безгранично доверял. В следующем году Сулла сделал его проконсулом Дальней Испании, отправив вместе с ним значительную армию, состоявшую из двух легионов и большого количества вспомогательных частей. Главной задачей Метелла была война с Серторием.

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

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

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

Способ создания Серторием своего сената неизвестен. Сулла, захватив власть, увеличил число сенаторов до 600, как в свое время хотел сделать Друз. Но Друз не определил критерии и способ отбора, а Сулла юридически оформил это пополнение как выборы всадников по трибам. Серторий был лишен возможности провести подобное голосование. По-видимому, он отложил легализацию своего сената до победы над сулланским правительством. Местный сенат Серторий считал высшим авторитетом во внешней и внутренней политике, хотя на деле он мог и оказывать на сенаторов довольно сильное воздействие, добиваясь своих целей даже вопреки воле сенаторов, как это произошло при обсуждении договора с Митридатом. Из числа своих приверженцев Серторий назначал также преторов и квесторов. Они помогали Серторию в армии, а в случае необходимости могли действовать самостоятельно. Кроме военных функций они исполняли и гражданские, управляя от имени полководца теми или иными территориями. Имелись у Сертория и другие должности. Так, известен некий Гай Инстей, который был префектом всадников и тоже порой действовал самостоятельно.

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