Военную службу он начал во время войны с кельтиберами и, вероятно, прослужил несколько лет до прибытия в Испанию Сципиона Эмилиана. Марий с готовностью воспринял более строгую дисциплину нового командующего. Существует история о том, как он произвел хорошее впечатление во время одной из частых инспекций Сципиона армейского вооружения, снаряжения и багажа. В другой раз он участвовал в бою один на один и победил. Консул лично видел этот поединок, подвиг принес Марию знаки отличия и другие почести. Марию было в это время двадцать три года, и, вероятно, он уже занимал должность трибуна. Сципиону исполнилось, столько же, когда он прославился, выиграв бой один на один. Подобная храбрость, судя по всему, считалась уместной для офицеров подобного ранга, даже если сами главнокомандующие и их старшие подчиненные уже не шли на такой риск.
{115}Обычно честолюбивых молодых людей, которые не отличались высоким происхождением, большим состоянием и влиянием, поддерживали могущественные семьи. Марий и его родители являлись клиентами Цецилиев Метеллов, знатного плебейского рода, представители которого часто занимали высокие посты. В 119 г. до н. э. Луций Цецилий Метелл Делматик был выбран консулом, и, возможно, именно он помог Марию стать народным трибуном. Занимая эту должность, Тиберий Гракх проводил свою программу реформ, но человеку из такой семьи, как Марий, было не под силу повторить что-нибудь подобное. Марий внес несколько законопроектов, один из которых послужил причиной его конфликта с собственным покровителем. Этот инцидент завоевал Марию репутацию человека мужественного, с независимыми взглядами.
Несмотря на это, мало кто мог предвидеть его будущую славу, и он проиграл выборы на должность эдила, а в 115 г. до н, э. с помощью подкупа избирателей сделался претором. Его отправили руководить Дальней Испанией, где он провел несколько небольших операций, сражаясь с бандами разбойников, но у него не было возможности завоевать большую славу и состояние.
Приблизительно в это время он женился на Юлии из рода Юлиев Цезарей — старинной патрицианской семье, утратившей былой авторитет. В течение всего II века до н. э. только один из ее членов сумел стать консулом. Это был удачный альянс, но он едва ли гарантировал значительное продвижение в политике. Скорее всего, Марий не раз безуспешно пытался стать консулом в последующие годы, но его карьера приостановилась до тех пор, пока военный кризис в Нумидии не представил ему возможности привлечь к себе внимание общественности.
{116}Успешному вторжению Сципиона в Африку в 204 г. до н. э. значительно способствовал переход на сторону римлян нумидийского царевича Масиниссы, который впоследствии в качестве награды за помощь получил престол в своем сильно разросшемся царстве. После Второй Пунической войны Нумидия оказалась полезной для Рима, служа одним из главных препятствий восстановлению могущества Карфагена. И Масинисса, умерший во время начала Третьей Пунической войны, и его сын Миципса по первому требованию обеспечивали римлян зерном, войсками и слонами. Племянник Миципсы Югурта привел слонов и пеших стрелков на помощь Сципиону Эмилиану во время кампании в Нуманции, при этом Югурта сумел заслужить у римлян высокую оценку за мастерство и мужество.
В 118 г. до н. э. царь Масинисса умер, завещав свое царство Югурте, которого он усыновил, и своим родным сыновьям Адгербалу и Гиемпсалу. Последний скоро был убит по приказу своего кузена. Адгербал сбежал в Рим, и сенат постановил, что царство Масиниссы должно быть разделено поровну между двумя соперниками. Но Югурта вскоре нарушил перемирие. Такого рода борьба внутри династйи была обычным явлением среди нумидийских и мавританских царских семей. Когда-то именно подобный спор побудил Масиниссу искать помощи у Сципиона. Однако в 112 г. до н. э. Адгербала осадили в Цирте, среди жителей которой было много римских и италийских торговцев. Именно они в основном обороняли город, и после капитуляции были перебиты людьми Югурты.
Известие об этом привело Рим в ярость. Особенно были возмущены всадники, являвшиеся главами больших торговых компаний, которые вели дела в этом регионе, именно их люди оказались среди погибших. При этом сильное недовольство охватило все слои населения Рима. Эти настроения подогревались трибуном Гаем Меммием (вероятно, это он заслужил презрительный отзыв Эмилиана во время осады Нуманции) до тех пор, пока сенат не решил послать в Северную Африку консула Луция Кальпурния Бестию с армией. Югурту убедили приехать в Рим, где он занялся открытым подкупом влиятельных сенаторов и даже организовал убийство члена своей семьи, который находился здесь в изгнании. Покидая Рим, он, рассказывают, бросил презрительную фразу: «Рим — продажный город, и ему придет конец, как только найдется покупатель!» После этого визита ярость народа удвоилась и теперь главным образом была направлена на сенат, который проявил свою явную некомпетентность и коррумпированность.