Вскоре, однако, Серторию пришлось сменить тогу на военный плащ — шла война с кимврами и тевтонами. Он поступил под командование Квинта Сервилия Цепиона (
6 октября 105 г. войско Цепиона была наголову разгромлено кимврами, тевтонами и их галльскими союзниками в битве при Араузионе на р. Родан, которая стала одной из самых тяжелых катастроф в истории римской армии. Серторий был ранен в бою и потерял коня, но сумел, преодолев сильное течение, переплыть Родан и сохранить панцирь и щит (
Если верна гипотеза о том, что нурсиец стал клиентом Цепиона, то катастрофа при Араузионе имела для него одно неприятное последствие: его предполагаемый покровитель был осужден как виновник поражения (Цепион не хотел согласовывать свои действия с менее знатным консулом Гнеем Маллием Максимом, если тот ему не подчинится). Его также подозревали в причастности к разграблению разбойниками сокровищ толозского храма, доставку которых он должен был обеспечить из Толозы в Массилию (Oros., V, 15, 25;
После этих событий командование перешло к герою Югуртинской войны Гаю Марию, который был избран консулом на 104 г. и занимал эту должность 5 лет подряд (!). После тщательной подготовки армии и серии маневров он вступил в 102 г. в сражение с тевтонами при Аквах Секстиевых. В первый день боя войска Мария нанесли серьезный урон их союзникам галлам-амбронам. Несмотря на успех, римляне провели ночь в тревожном ожидании (Plut. Mar., 20, 1–3). Вероятно, именно тогда и совершил Серторий свой второй из известных нам подвигов. Переодевшись в галльское платье и выучив самые ходовые выражения языка амбронов, он пробрался в их лагерь, добыл там ценные сведения о противнике и благополучно вернулся к своим. «На этот раз Серторий был удостоен награды, — пишет Плутарх, — а так как во время дальнейших военных действий он проявлял разум и отвагу, то приобрел славу и стал пользоваться доверием полководца» (Plut. Sert., 3,2. — Здесь и далее этот источник цит. в пер. А. П. Каждана). Более об участии нурсийца в войне с кимврами и тевтонами ничего неизвестно.
Казалось бы, у Сертория появился новый покровитель — Марий — взамен опального Цепиона. Однако, как показали события 87 г. (см. ниже), отношения между ними оставляли желать лучшего. Нужно учитывать, что после разгрома движения Сатурнина влияние Мария упало, а связи с враждебной ему фамилией Цепионов Серторий, можно думать, сохранял.
Как складывалась его судьба в последующие за победой над кимврами и тевтонами два-три года, источники не сообщают. В 90-х же гг. он оказался в ранге военного трибуна под командованием консула 98 г. Тита Дидия в Испании (