Да он и не скрывал своих намерений. После истечения срока трибуната он претендует на должность эдила — магистрата, занимающегося городскими делами, важная ступень для дальнейшей карьеры. Но безуспешно. И лишь после того, как он женился на тетке Цезаря, и при поддержке семейства Юлиев, а через него и некоторых патрицианских кругов он становится претором. Когда истекает срок на этой должности, то по жребию его направляют в так называемую Внешнюю Испанию, где он успешно расправляется с местными разбойниками.
Но вернемся к Югуртианской войне, во время которой Гай Марий сделал решающий шаг в своей карьере.
Военные действия в африканской пустыне затягивались и не сулили честолюбивому выскочке никаких перспектив. Но он не терял времени даром. Прекрасно понимая силу народного мнения, вместе с простыми легионерами копал рвы, ел вместе с ними то, что ели они, и спал на земле на подстилке. Ну и вел при этом с ними разговоры о том о сем. Вскоре он стал любимцем всего войска, а в письмах, которые легионеры отправляли из Африки в Рим, прямым текстом сообщалось, что лучше Мария военачальника они не знают и конца африканской кампании не предвидится. А вот если его избрать консулом, то победа над Югуртой обеспечена. И когда в Риме началась предвыборная суета, он обратился к Метеллу, но тот сказал, что скорее его малолетний сын станет консулом, нежели Марий. Не только Метелл, но и другие влиятельные патриции иронично отнеслись к домогательствам Мария на консульство. Более того, Метелл не собирался отпускать его в Рим и лишь за двадцать дней до выборов дал согласие, очевидно полагая, что за столь короткий срок его помощник если и успеет добраться до Рима, то на агитацию времени у него не останется точно.
Но судьба благоволила Марию. Он быстро добирается до У тики. Там совершает жертвоприношение, и ему предсказывают блестящее, просто невероятное будущее. Впоследствии Марий говорил, что ему было обещано семикратное консульство, но это казалось невероятным даже его ближайшим сторонникам. До поры до времени.
Попутный ветер за четыре дня позволяет ему пересечь Средиземное море. И вот он в Риме. И сразу же выступил перед народом, смешав Метелла с дерьмом и пообещав быстро закончить войну с Югуртой. Народ с упоением слушал грубые слова Мария, поливавшего последними словами знать. На фоне риторических красот, которыми блистали его соперники, это был свежий ветер перемен. И конечно же, Мария избирают консулом.
Сенат оставляет Метелла полководцем, но народное собрание постановляет, чтобы Марий вел боевые действия.