Когда Цинна в 87 г. выступил против учреждений Суллы, то к нему (Цинне) примкнул Серторий. Вместе они сражались против Октавия, подверглись изгнанию и затем снова с Марием возвратились в город. Он возражал против возвращения Мария, но безуспешно. В Риме Серторий старался положить предел свирепым неистовствам Мария и велел наконец избить его злодейскую шайку, численностью в 4 тыс. человек, в их лагере. Когда после смерти Цинны для борьбы с возвратившимся из Азии Суллой поставлены были во главе народной партии большей частью люди слабые и неспособные, как Норбан, Сципион, молодой Марий, и люди эти, не внемля увещеваниям Сертория, портили все дело своей неумелостью, то он, отчаявшись в спасении Италии, поспешил в Испанию, которую его единомышленники предоставили ему как провинцию. Он старался отстоять, по крайней мере, эту страну для своей партии и приготовить там своим друзьям убежище, если бы дело их было проиграно в Риме.
Как только Сулла полностью овладел Италией, отправил К. Аррия со значительными силами в Испанию против Сертория, и последний чувствовал себя слишком слабым, чтобы держаться против него. Он с отрядом приблизительно в 3 тыс. человек переправился в Африку и некоторое время скитался в сообществе киликийских гератов по мавританскому берегу и по островам между Африкой и Испанией, пока снова вступил на берег у Бетиды (Квадалкивира). Здесь он встретился с матросами, которые только недавно прибыли с Атлантических (Канарских) островов, островов блаженных, и много порассказали ему об их великолепии и плодородии. Тут в нем проснулось желание основать себе там жилище, чтобы вдали от суеты мира прожить дни свои в покое. Вследствие этого от него отделились киликийцы, заботившиеся не об успокоении, а о добыче, и его собственные войска также не одобрили его намерение, так что он снова пошел с ними на мавританский берег и принял участие в войне, которую вели между собой два претендента на престол этой страны. Он завоевал город Тингис (ныне Тангер) и утвердился в нем. В то время когда он еще раздумывал, куда бы ему отсюда направиться, пришли посланные от лузитанцев и просили его стать во главе их полководцем в войне, которую они вели против Сулловых войск. Серторий снова ободрился духом; он мог надеяться опять завладеть Испанией при помощи многочисленных тамошних племен. С отрядом в 2600 человек, названных им римлянами, хотя среди них было 700 ливийцев, он переправился в Лузитанию, где туземцы подкрепили его 4 тыс. человек пехоты и 700 всадниками. Так образовалось ядро того войска, с которым ему предстояло наводить страх на своих противников (81 г.).