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