Много средств потратил Серторий на подкуп вождей и старшин местных племен. Он охотно набирал солдат-испанцев, назначая их на важные посты. Но ответственные должности все же сохранялись за римлянами. Тем не менее испанцы верили Серторию, видев в нем нового Вириата.
Серторий создал в Испании правительство, наподобие римского, учредил сенат и органы власти. Словно римского консула Сертория сопровождала почетная охрана в двенадцать ликторов, которые несли на плечах связки розог с воткнутыми в них топориками в знак власти Сертория над жизнью его подданных.
Серторий разделил территорию полуострова на две провинции: Лузитанию со столицей в Эбро (ныне Эвора в Португалии) и Кельтиберию - с центром в Оске (ныне Уэска в Кастилии). Серторий начал чеканить свою монету.
Несколько лет Серторий управлял Испанией. Он стремился насаждать культуру римлян, заставлял своих приближенных подражать их обычаям, открывал школы и требовал, чтобы кругом звучала только родная ему латинская речь. Воинов он обучал по римским правилам и в армии ввел римский военный строй и жесткую дисциплину.
К Серторию со всех сторон стекались тысячи добровольцев-испанцев. У него теперь образовалось сильное войско. Скоро он вторгся в римскую провинцию - Дальняя Испания. Наступление застало сулланцев врасплох. Оставив на поле боя тысячи трупов, они в панике бежали. Почти вся провинция досталась войску Сертория.
Не давая противнику передышки, Серторий появился в провинции Иберия. Ее наместник Марк Домиций Кальвин получил приказ Суллы любой ценой остановить противника. На помощь Домицию Кальвину прибыли три легиона. Командующим всеми силами, действующими против Сертория, был назначен опытный военачальник Квинт Метелл.
Но напрасно сулланские командиры пытались остановить наступление врага. Серторий одержал новые победы: пал в бою Домиций Кальвин, сокрушительное поражение потерпел Метелл.
Серторий не давал отступавшим римлянам ни минуты покоя. Он был замечательным руководителем партизанской войны: уклоняясь от сражений, лишал римлян снабжения, отрезая все пути подвозу продовольствия, окружал небольшие части и уничтожал их, неожиданно появлялся там, где неприятель не ожидал его.
Успехи Сертория не вскружили ему голову. Он по-прежнему был прост в обращении с населением, суров с нарушителями дисциплины. Силы его росли. Через два года после высадки на пуссынном берегу Лузитании ему принадлежала почти вся Испания. Союзники Сертория - пираты подстерегали римские суда, захватывая, уничтожая их, снабжали испанцев оружием и продовольствием. Серторий направил своих представителей в Галлию, призывая народ этой страны поднять восстание против Рима и присоединиться к испанцам. Вскоре в районах, соседних с Испанией, появились партизанские отряды галлов. Горные проходы Пиренеев оказались в руках восставших. В разгар побед Сертория скончался Луций Корнелий Сулла. Римская народная партия попыталась свергнуть аристократов - сторонников Суллы, но потерпела неудачу. Тогда один из виднейших вождей демократов, Марк Перперна, привел свои войска в Испанию к Серторию (77 г. до н. э.). Серторий ожидал Перперну в своем лагере. Воины-испанцы находились в возбуждении - к ним прибыло подкрепление из Италии. Шатер Сертория был украшен венками. У входа толпились командиры. Выстроились ликторы. Центурион доложил, что Перперна сейчас прибудет. Заиграли трубы. Восторженные клики приветствовали легионеров Перперны отборных воинов, некогда сражавшихся под командованием самого Мария. Серторий обнял Перперну и увел его к себе в шатер. Перперна - надменный и заносчивый, честолюбивый и бесчестный - был полной противоположностью Серторию. Очень скоро между обоими полководцами начались нелады. Силы Рима росли. Сенат не ограничился присылкой подкреплений Метеллу, а направил против Сертория новую армию, которой командовал молодой Гней Помпеи. Разведчики сообщили Серторию о приближении крупных сил врага, и опытный военачальник решил отступить, не принимая боя. Своенравный Перперна отказался выполнить приказ начальника, начал битву с Помпеем и вскоре был разбит. Когда остатки разгромленного войска прибыли в лагерь, полководец вышел из шатра навстречу Перперне. Воины подвели к нему двух лошадей. Одна из них была старая кляча, а другая - молодая кобыла с пышным хвостом и густой гривой. Серторий предложил легионеру, известному своей необычайной силой, подойти к старой лошади, а к молодой подошел карлик. Обоим было приказано вырвать у коней хвост. Силач схватил клячу за хвост и дернул за него изо всей силы. Несчастная лошадь зашаталась, но воин так и не смог вырвать У нее хвост. Карлик же начал выщипывать волосок за волоском, и скоро кобыла лишилась хвоста.
