Пока Серторий готовился к тому, чтобы сделать из Испании плацдарм для новой войны, в Италии Сулла одержал полную победу. В 82 г. до н. э. он захватил Рим и обрушил на римлян жесточайший террор, перед которым померкли все воспоминания о марианском терроре. Затем он ввел в этот террор своеобразный порядок, составив так называемые проскрипционные списки, в которые вносились имена тех, кто был объявлен вне закона. В эти списки, естественно, попал и Серторий. В конце 82 г. до н. э. Сулла стал пожизненным диктатором, что окончательно оформило его единоличную власть. В следующем году Сулла назначил Гая Анния Луска, одного из своих сторонников, наместником Испании в ранге проконсула, распространив, по-видимому, его власть на обе испанские провинции. Еще до этого, понимая неизбежность подобного поворота дел, Серторий послал отряд из 6 тысяч воинов во главе с Ливием Салинатором занять горные проходы. И когда Анний со своей армией подошел к Пиренеям, прорваться через эти проходы он не смог. Тогда в ход пошло коварство. Некий Кальпурний Ланарий, видимо не без поощрения Анния, убил Ливия, и его воины, лишившись командира, самовольно покинули свои позиции. После этого армия Анния свободно перешла Пиренеи и вторглась в Испанию. Серторий пытался оказать сопротивление, но неудачно. Его войска были разбиты, а сам он бежал в Новый Карфаген, бывший в то время столицей Ближней Испании. Но и там отсидеться ему не удалось. Его армия была разбита, а получить значительную поддержку от населения Испании, как от переселенцев, так и от туземцев, он не смог: времени для укрепления своего авторитета среди них не хватило. И Серторий решил бежать. С тремя тысячами воинов, сохранивших ему верность, он сел на корабли и направился в Африку.
Эти события нанесли тяжелый удар по Серторию и его надеждам. Он метался, не зная, что предпринять. В Африке он сначала тоже потерпел неудачу, когда его воины проявили беспечность и на них напали мавританцы, убив многих из них. Тогда Серторий с оставшимися воинами снова направился к испанским берегам, но высадиться не смог. С помощью присоединившихся к нему киликийских пиратов он сумел захватить остров Питиуссу, разбив оставленный там Аннием гарнизон, но закрепиться там не смог, ибо входе морского сражения с посланным Аннием флотом его корабли были бурей отнесены к скалистому берегу, где многие из них погибли. Оставшиеся корабли Сертория несколько дней носило бурей по волнам Средиземного моря, пока он не сумел пройти пролив между Европой и Африкой (Гибралтарский) и высадиться в районе устья Бетиса. Там он встретил моряков, приплывших откуда-то с океанских островов; они рассказали ему об Островах блаженных, расположенных в океане.
Представления о существовании за пределами обитаемого мира какой-то счастливой страны, где нет места ужасам существующего современного мира, были свойственны разным народам. В греческой литературе они выражены уже Гомером в «Одиссее» в виде повествования о Елисейских полях, являвшихся обиталищем душ героев, не подверженных обычной участи мертвеца уйти в мрачное царство Аида. Такие представления особенно оживают во времена социальных и политических бурь, когда порой кажется, что никакого другого спасения уже нет и быть не может. Но если гомеровские герои, как, например, спартанский царь Менелай, должны уйти туда только после смерти, то в период жизни Сертория Острова блаженных представлялись уже реальным местом, куда и при жизни вполне можно добраться и где такого путешественника не настигнут земные власти. При этом, видимо, старые утопические мечты сливаются с туманными сведениями о каких-то реальных островах в Атлантическом океане. Описание этих островов с их мягким и влажным, но не дождливым климатом, плодородной землей, слабой разницей между временами года слегка напоминает Канарские острова. И вот туда Серторий, измученный постоянными неудачами, и решил отправиться, ибо там наконец надеялся найти убежище, где его не достанут ни неверные союзники, ни длинные руки Суллы.
Однако спутники Сертория его не поддержали и даже были готовы покинуть его; видимо, жажда немедленной добычи оказалась сильнее надежды найти мир и покой за краем земли. Сразу же Сертория покинули его союзники — киликийские пираты. Они направились в Африку, где свергнутый с трона мавританский царь Аскалид обратился к ним за помощью. И Серторий тоже решил вмешаться в мавританские дела, выступив против Аскалида.
Прибыв в Мавританию, он почти сразу же вступил в бой. Армия Аскалида была разбита, и сам он со своими братьями бежал в город Тингис на берегу океана. Серторий со своим отрядом осадил Тингис. Сулла, понимая, что Серторий в случае победы сможет превратить Мавританию в свою опорную базу, направил туда Пакциана с сильным отрядом. Это был богатый и крупный землевладелец Южной Испании, ярый сторонник Суллы. По-видимому, Сулла торопился покончить с Серторием, не теряя времени, которое понадобилось бы для посылки армии из Италии. Но Серторий разбил войска Пакциана, а сам Пакциан был убит. После этого он продолжил осаду Тингиса и взял его. Эта победа сделала Сертория фактически господином Мавритании. Но победы в Африке снова вдохновили его, и он опять был готов сделать все, чтобы свергнуть ненавистный сулланский режим. Поэтому он ограничился восстановлением власти местного царя, взамен получив от него мавританских всадников и какую-то долю добычи. Он стал готовиться к войне. Но очень скоро положение изменилось радикально. В 80 г. до н. э. Серторий получил предложение лузитан возглавить их в восстании против римлян. И он, не колеблясь, принял это предложение.
Лузитаны жили на западе Пиренейского полуострова. В течение многих лет и десятилетий они вели упорную борьбу с римлянами. К 80 г. до н. э., казалось, борьба закончилась, и лузитаны подчинились, их территория была включена в провинцию Дальняя Испания. Но гражданская война, по-видимому, возбудила надежды лузитан вернуть себе независимость. Лузитаны, как и все испанцы, в своих отношениях с Римом избирали себе патронов из числа хорошо им известных деятелей. Серторий к этому времени прославился в Испании своими подвигами и воинским умением, давшими ему не только славу у соотечественников, но и уважение испанцев, а во время своего недавнего пребывания в качестве наместника он продемонстрировал качества умелого и справедливого администратора, что снискало ему расположение населения. Для Сертория приглашение испанцев стало единственной возможностью продолжить борьбу с сулланским правительством. Пропретором Дальней Испании был в это время Люций Фуфидий, ярый сулланец, который и подал в свое время Сулле мысль создать проскрипционные списки. Ближней Испанией управлял другой сулланец — Марк Домиций Кальвин. Так что для Сертория борьба с ними была не мятежом против собственного государства (чем она реально, конечно, являлась), а продолжением гражданской войны.
Со своими воинами, в число которых входили и мавританские всадники, он, оставив в Африке небольшой отряд на случай, если придется вернуться, ночью переправился через пролив. Лузитаны с восторгом приняли его и провозгласили своим верховным вождем. Сил у Сертория было немного: 6600 пехотинцев, 4 тысячи из которых были лузитанами, и 1400 всадников (700 лузитанских и столько же мавританских). Тем не менее он активно начал военные действия. В морском сражении был разбит флот под командованием Марка Аврелия Котты, а затем в упорном сражении на берегах Бетиса Серторий разбил армию Фуфидия. Фуфидий обратился за помощью к Кальвину. Стремясь не допустить соединения вражеских сил, Серторий направил против Кальвина часть своей армии во главе с Люцием Гиртулеем. Гиртулей был активным врагом Суллы, но большой карьеры в антисулланской коалиции не сделал. В 86 г. до н. э. он был квестором, и Серторий сохранил за ним этот ранг. Вместе с Серторием он покинул Италию и оставался ему верным соратником, несмотря на все превратности. В армии Сертория Гиртулей пользовался огромным авторитетом. И позже Серторий не раз поручал ему командование самостоятельными частями войска. А когда много позже Гиртулей погиб, Серторий убил вестника его смерти, чтобы слух о гибели Гиртулея преждевременно не распространился в армии.
