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