Первые симптомы будущего кризиса начались уже при жизни Суллы. В 80 г. восставшие лузитане пригласили в качестве командующего Квинта Сертория, бывшего марианского наместника провинции. Квинт Серторий был последним из крупных полководцев марианской партии. Он родился в 123 г. в Нурсии, со 105 г. служил в армии Цепиона в Галлии, со 104 г. — в армии Мария и участвовал в битве при Аквах Секстиевых. В 98 г. он служил в армии Т. Дидия в Испании, где пробыл до 94 г. В 90 г. Серторий был квестором в Цизальпийской Галлии, стать трибуном в 88 г. ему помешал Сулла. В 87 г. он стал одним из лидеров марианцев во время осады Рима, а затем вместе с Цинной прекратил марианские репрессии. После смерти Цинны, Серторий отошел от руководства и был назначен наместником Испании. В 83 г. он был пропретором в Hispania Ulterior, в 82–81 гг. готовился к продолжению борьбы с сулланцами, но в 81 г. был выбит из провинции сулланцем Г. Аннием и находился в Мавретании. В 80 г. Серторий высадился в Бетике, возглавил лузитан и разгромил армию наместника Фуфидия. В 79 г. с 6 легионами в Бетику прибыл Кв. Цецилий Метелл, однако и ему не удалось разбить Сертория. Началась затяжная война, в которой марианский полководец активно использовал испанские племена, составлявшие основу его армии.
Серторий сумел соединить движение туземного населения с действиями римской эмиграции. Во главе встал эмигрантский сенат и назначенные им магистраты{143}
.[29] Серторий считался проконсулом, на подконтрольных ему территориях испанцы получали римское гражданство, создавались провинциальные собрания. В городе Оске появилась школа для детей испанской знати. Самого Сертория окружало несколько тысяч солдуриев, готовых отдать за него жизнь. Ядром армии были марианцы и романизированные жители Бетики, но Серторий широко использовал туземные войска и их партизанскую тактику[30]. В 79 г. армия Метелла вторглась в Лузитанию, но, благодаря партизанской тактике, Серторий заставил ее отступить. В том же году серторианцы начали наступление в Ближней Испании и разбили сулланского наместника Домиция Кальвина.На Востоке начинался расцвет пиратства, особенно в Киликии и на Крите. Пиратство процветало и ранее, но именно после гражданских войн эскадры морских разбойников резко усилились за счет беглецов из Италии, Испании и Азии. Победа Суллы придала пиратству новое дыхание. Пиратские государства стали бросать вызов римлянам, их поддержали племена и государства в Далмации, Македонии и Исаврии. В 80 г. в Далмации начала операции армия Гая Коскония, в 79 г. назначенный наместником Македонии Аппий Клавдий начал операции против фракийцев. В том же году второй консул этого года, П. Сервилий Ватия, был послан в Исаврию.
Сервилий был одним из ведущих лидеров клана Метеллов. Его отец, претор 114 г. П. Сервилий Ватия, был женат на Цецилии Метелле, дочери Метелла Македонского. Сервилий родился в 134 г., в 100 г. он участвовал в борьбе с Сатурнином, в 90 г. был претором и участвовал в Союзнческой войне. С ервилий был достаточно близок к Сулле, в 88 г. тот хотел сделать его консулом на 87 г., но Сервилий потерпел неудачу (Plut. Sulla, 10). В 87 г. Сервилий командовал одной из армий оптиматов, но был разбит у Аримина (Licin. 27 Bonn), бежал к Сулле в Грецию, вернулся вместе с ним и участвовал в гражданской войне. В 82 г. он одержал победу у Клузия (Veil., II, 28; Plut. SuU, 28). Сервилий и Аппий Клавдий стали консулами сразу после Суллы и Метелла Пия. Сервилий, видимо, оказался более или менее непричастен к террору Суллы. Принадлежа к Метеллам, он скорее всего, смыкался с военными, ориентируясь на державные интересы и умеренные реформы, это был способный полководец и именно с него Цезарь начал разыгрывать свою сложную партию с сулланской элитой.
В 79–78 гг. Сервилий разбил пиратский флот и начал наступление против пиратского предводителя Зеникета, заняв его крепости Олимп, Корик и Фаселиду в восточной Ликии и Атталию в Памфилии. Зеникет погиб. Легионы Сервилия двинулись в Исаврию, перешли через Тавр и взяли Исавру и Ороанду. Война закончилась к 74 г., когда римляне подавили сопротивление противника в Ликии, Памфилии и западной Киликии, ограничив пиратство приморскими областями. Кроме того, Сервилий сумел подчинить ряд внутренних областей Малой Азии, создав возможность наступления на центральную часть державы Митридата, которое вели уже другие полководцы. Возможно, это был первый серьезный успех римской армии в постсулланский период.