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