Помпей отдавна беше разрешил проблема с легатите, назначавайки само пиценци или италийци; най-висш чин след него имаха Луций Афраний и Марк Петрей — все стари кучета от Пицен, служили в легионите на Помпей или на баща му. Към тях се причисляваха другарят на Цезар от Митилена Авъл Габиний, също от пиценски произход, Гай Корнелий — човек, който нямаше нищо общо с патрициите Корнелий, и Децим Лелий, който пък нямаше общо с онази богаташка фамилия, издигнала се по време на Сципион Африкански Старши. Всички офицери в армията на Помпей или бяха доказали воинските си способности, или ги очакваше бляскаво бъдеще в кариерата, в същото време нито един от тях не се радваше на високо обществено положение, с изключение може би на Авъл Габиний (чиито баща и чичо бяха в сената), затова и никой не можеше да разчита на издигане в политиката без щедрата подкрепа на патрона си Помпей.
Нещата се развиваха доста добре. Помпей напредваше бързо по крайбрежния път, шестте му легиона заедно с конницата се озоваха при Дертоза на северния бряг на Ибер, без да срещнат съпротива. Докато се опитваше да преброди реката, около два легиона войници, предвождани от Херений, се опитаха да го нападнат, но той с лекота ги отблъсна. Младият пълководец придоби самочувствие и той продължи на юг, изпълнен с оптимизъм. Скоро Херений отново се появи, този път подкрепен от два от легионите на Перперна, но когато авангардът му даде първите убити, той побърза да се оттегли.
Помпеевите съгледвачи вършеха чудесна работа. Докато той се отдалечаваше от бреговете на Ибер, те му донасяха вести, че Херений и Перперна се били спотаили в големия град Валенция — на повече от сто километра на юг. Градът се намираше на брега на река Турис, околните земи бяха много плодородни и гъсто населени. Помпей побърза да прогони по-бързо врага от стратегическата му позиция. Когато се озова под стените на Сагунт — близо до устието на малка рекичка, напояваща бедната област, верните съгледвачи го уведомиха, че самият Серторий бил далеч и не би могъл да помогне на Херений и Перперна, ако бъдат обсадени във Валенция. Серторий очевидно се опасявал, че Метел Пий може да нахлуе в Северна Испания, затова бил разположил армията си по горното течение на река Салон, при град Сегонция, откъдето най-лесно би могъл да препречи пътя на Прасчо, ако реши да прехвърли относително ниските планини между Таг и Ибер. „Добре замислено, Серторий — разсъждаваше самодоволно Помпей, — но не трябваше да оставяш толкова далеч Херений и Перперна!“
Беше средата на май и Помпей започваше да усеща колко жестоко е за войската изпепеляващото испанско слънце. Започваше да разбира и колко много вода е нужна на войниците му, и колко бързо свършват хранителните запаси. До жътва оставаха няколко месеца, а градовете, които римските легиони бяха подминали, бяха запазили твърде малко зърно в хамбарите си, за да нахранят армията. На картите испанското крайбрежие изглеждаше богато и плодородно, но в действителност се оказваше доста по-бедно от родната Италия; Помпей винаги беше смятал родните си земи по адриатическото крайбрежие за бедни и безлюдни, но те се оказваха истински рай в сравнение с бреговете на Източна Испания.
Сагунт искаше да докаже лоялността си към Рим, но нямаше с какво — хамбарите бяха празни. Пирати били разграбили крайградските силози, жителите на града имали дневни дажби, с които трябвало да оцелеят до новата реколта. Оставаха само Валенция и околните поля: Помпей нямаше време — строи легионите си и продължи похода на юг.
Високите планини, които се виждаха на хоризонта, говореха, че целият полуостров е насечен от била и долини, които нямаше да позволят на Серторий, окопал се от началото на май край Сегонция, да се притече на помощ на Валенция по-рано от края на юни. Помпей също не вярваше, че който и да е пълководец на земята може да осъществи по-бърз преход от него самия, затова им се доверяваше; малко го занимаваше мисълта дали те самите не са се подлъгали, или дали не работят за Серторий. Така или иначе, само ден, след като беше напуснал околностите на Сагунт, Помпей научи, че противникът не само се намира между него и Валенция, но точно в този миг е обсадил лоялния на Рим град Лаврон!
Това, което Помпей не беше взел под внимание, бе, че Серторий живее на полуострова от дълги години — че е имал случай да научи всяка котловина, всеки дол, всяка пътека от средиземноморските брегове чак до западните предели на Испания; че може да си позволи светкавични преходи, защото не му е нужен обоз — всяко село, всяка колиба с готовност ще го снабди с продоволствия. Сред келтиберите и лузитаните не се намираха хора, които да се радват на римското присъствие в Испания — за тях отдавна беше ясно, че римляните са дошли само за да разграбят богатите залежи на страната. Затова на Серторий се гледаше като на дар, спуснат на всички местни жители от боговете. Кой друг познаваше по-добре римляните от него — родения римлянин?