Поэтому Сципион открыл храброму и по-крестьянски сметливому Марию доступ к офицерскому чину. Сын батрака не упустил возможности выдвинуться, став через некоторое время одним из самых лучших и отважных штабных офицеров главнокомандующего. Наблюдая за энергичным, упорным и трудолюбивым молодым человеком, Сципион прочил ему блестящую карьеру. Эти разговоры еще больше разжигали честолюбие Мария, стремившегося сравняться со знатью в почестях, титулах и богатстве, войти в аристократическую среду как равный, а, может быть, и как первый среди равных. Он надеялся при поддержке и покровительстве Сципиона достигнуть на политическом поприще таких же успехов, как и на военном.

Но надежды Мария не оправдались: покровитель рано умер, и он лишился могущественной поддержки. Несмотря на это, Гай все же попытался начать политическую высокомерием и чванством римской терпеть обиды и унижения.

Его простые крестьянские манеры, вполне пригодные в военном лагере, казались смешными в столице. Все попытки Мария сблизиться со знатью римские аристократы встречали презрительными насмешками. Именно под влиянием этих обид в характере Мария появились и развились отрицательные черты: к трудолюбию, упорству, энергии, храбрости и здравому смыслу римского крестьянина прибавились хитрость, алчность, жестокость, злобная завистливость и подозрительность.

Ценой больших унижений Марию удалось, наконец, заручиться поддержкой знатного семейства Цецилиев Метеллов. Благодаря их помощи Гай выставил свою кандидатуру на выборах народных трибунов.

В это время в Риме шла борьба между правителями-аристократами и народной партией, стремившейся к власти. Став трибуном, Марий внес в сенат законопроект, ограничивавший влияние римской знати при выборах должностных лиц. Несмотря на сопротивление аристократического сената, он добился проведения закона в жизнь. Этим Гай снискал к себе симпатии народной партии, но аристократы отвернулись от него.

Напрасно Марий пытался заручиться поддержкой знати, помешав в сенате проведению закона о даровой раздаче хлеба римской бедноте. Этим он добился только того, что от него отвернулись и демократы.

После окончания срока полномочий трибуна Марий выдвинул свою кандидатуру на должность эдила. Однако, потеряв симпатии как аристократов, так и демократов, он провалился на выборах. Его даже привлекли к суду по обвинению в подкупе избирателей.

Казалось, политическая карьера была кончена и оставалось только заниматься финансовыми спекуляциями, с помощью которых Гай Марий уже сумел сколотить себе порядочное состояние. Однако и на этот раз судьба улыбнулась честолюбцу: ему удалось посвататься к Юлии, происходившей из знатного семейства Юлиев Цезарей. Женитьба на аристократке восстановила положение Мария в обществе, а родственные связи с семьей Юлиев позволили ему снова выступить на политической арене. В 115г. до н. э. Гай был выбран претором и назначен наместником в Испанию. Здесь он снова показал свои военные дарования в борьбе с испанскими повстанцами, которые вели против римлян партизанскую войну.

Вскоре после этого вспыхнула война в Африке. Нумидийский царь Югурта, возглавив свободолюбивых и отважных североафриканских кочевников, наносил римлянам поражение за поражением. После ряда неудач сенат решил направить в Африку лучшего полководца Рима, Цецилия Метелла, одного из покровителей Мария.

В поисках дельных офицеров для предстоящей кампании Метелл вспомнил о Марии, которому и была предложена должность в штабе. В войне с царем Югуртой Гай проявил блестящее военное дарование и прославился подвигами. В битве при реке Мутул римская армия одержала победу лишь благодаря стойкости и находчивости Мария. После этого сражения он становится первым помощником Метелла.

Вскоре, однако, отношения между главнокомандующим и помощником испортились: Марий решил воспользоваться трудностями войны с Югуртой, чтобы устранить Метелла и самому стать во главе армии. Честолюбивый офицер затеял интриги против своего начальника: он заискивал перед солдатами, в их присутствии порицал действия главнокомандующего, распускал грязные слухи о Метелле. Марий пользовался любым предлогом, чтобы доставить своему начальнику какую-либо неприятность.

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