их операцій і, що ще більш важливо, одружитися на Юлії, дівчині із старовинного і знатного патриціанського роду Юліїв. У 115-му році його обирають претором, а потім у званні пропретора призначають намісником у Дальню Іспанію. Тут в боротьбі з бунтівними іспанцями, він отримує можливість підтвердити свою репутацію хороброго воїна і талановитого полководця. Йому вдається завоювати повагу і любов солдатів. Він близький їм за походженням, вихованню і складом розуму. На рівних ділить з ними труднощі похідного життя, дивує своєю невибагливістю і витривалістю, незмінно піклується про підлеглих. Від інших римських воєначальників його відрізняє ще вчинене безкорисливе, навіть презирство до багатства і насолодами.
Після закінчення терміну намісництва Марій повертається до Риму і отримує від Квінта Цицелий Метелла, досвідченого полководця, переконаного і непримиренного аристократа, пропозиція супроводжувати його в Нумідію на війну з Югуртой в якості свого легата. У Плутарха є неясна згадка про те, що ще батько Марія служив будинку Метеллов. Можливо, що Квінт Метелл допоміг молодому Гаю вступити в іспанське військо римлян, незважаючи на відсутність у нього мінімально необхідного достатку. З іншого боку, той же Плутарх пише про зіткнення Марія, вже в якості трибуна, з Метеллом, якому він навіть нібито погрожував арештом. Тим не менш, Метелл бере Марія з собою в Нумідію і, цінуючи його військові заслуги, доручає відповідальне командування в бою. Але разом з тим дистанція між знатним аристократом і селянським сином залишається незмінною.
Югуртинская війна почалася в 111 р до н.е. Ця війна показала, як пала боєздатність римської армії. Нумідійський цар Югурта наносив римлянам жорстокі поразки, діючи не тільки збройними силами, а й силою золота, яке він щедро роздавав римським командирам і сенаторам. Дисципліна впала, військо був більш схожий на неорганізований натовп. У 109 р до н.е. в Африку був посланий Метелл, аристократ за походженням і затятий прихильник правлячої сенатської олігархії. За ним давно встановилася міцна репутація непідкупності. Вирушаючи в Африку, він не зважив з пануючими в його середовищі поглядами і призначив своїми найближчими помічниками людей хоча і незнатного походження, але здібних. Серед них був і Гай Марій. Прибувши до місця військових дій, Метелл насамперед прийняв найрішучіших заходів, щоб підняти дисципліну в розклалася армії. Зрозумівши неминучість поразки, Югурта запросив миру і погоджувався на будь-які умови, але Метелл двинув римську армію всередину Нумидии і в битві при річці мутулах наніс ворогу рішучої поразки. Чималу роль зіграв у цьому бої і Марій. Однак Югурта продовжував опір. Він вів партизанську війну при енергійній підтримці африканських племен. Метелл не вважав за можливе закінчити похід, що не захопивши самого Югурту, тому війна набула затяжного характеру. Метелл був неприємно здивований, дізнавшись від Марія про його непомірно честолюбному бажання балотуватися на чергових виборах консулів. До того ж це було викликом і порушенням традиції. Хоча після того як плебеї добилися повного зрівняння в правах з патриціями, будь-який громадянин Риму міг бути обраний консулом, досі на вищий державний пост насмілювалися претендувати тільки аристократи. Будь-які інші магістратури були вже доступні простому народу, але, як свідчить історик Саллюстій: «... консульську посаду знати поки зберігала за собою, ще передаючи її з рук в руки. Всякого нової людини як би він не прославився, які б подвиги не скоїв, вважали негідним цієї честі і як би оскверняти її ».
Римські історики стверджують, що зухвале рішення Марія було підкріплено пророкуванням великого і чудесного майбутнього, нібито зробленого якимсь гаруспік. Реакцію Метелла на претензії його легата і наслідки цієї реакції живо описується той же Саллюстій:
«Марій, -пише він, - побачивши, що слова гаруспік збігаються збігаються з тим, до чого його тягнуть таємні бажання, просить у Метелла відпустку, щоб випустити здобувачем на виборах. Хоча Метелл і був щедро наділений доблестю, спрагою слави та іншими якостями та іншими якостями, бажаними для чесних людей, він все ж відрізнявся презирливим зарозумілістю - загальним пороком знаті. Спантеличений незвичайним проханням, він спершу здивувався наміру Марія і як би по дружбі став застерігати його від настільки нерозумною затії і від прагнення, яке не відповідає його становищу ... Не переконавши його, Метелл обіцяв задовольнити його прохання; як тільки дозволять обставини. І згодом, коли Марій неодноразово звертався до нього з цим же проханням, Метелл, кажуть, радив йому не поспішати з від'їздом: для нього, мовляв, буде не пізно домагатися консулату разом з його сином. А той у цей час під початком батька там же проходив військову службу; і було йому років двадцять ». Природно, що Марій, якому уже сорок сім і чимало бойових заслуг за плечима, був ображений тако...
