Kr. e. 99-ben a dicstelen emlékű politikus bejelentette, hogy keletre utazik. Célpontja Galatia és Kappadókia volt, ahol állítása szerint áldozni kívánt egy esküvését teljesítve a Nagy Anyának, Kübelének. A háttérben azonban más motiválta. Felismerte, hogy hadvezérként van csak esélye támogatást szerezni, hiszen azon a téren sokkal jobban megállta a helyét, mint a politikain. Ezért aztán agitálni kezdett Pontosz királya, IV. Mithridatész udvarában, hogy megpróbálja a Római Köztársaság ellen ugrasztani. Sikert egyelőre nem ért el, bár a pontoszi uralkodó később valóban fegyvert fogott Róma ellen. Távollétében Mariust augurrá választották.

Hazatérve a Forum Romanum mellett építtetett házat, de ez sem segített mind jobban csökkenő népszerűségén. Keleti reményeit hajdani quaestora, Sulla sikeres intézkedései törték darabokra Kr. e. 92-ben. Hajdani alárendeltje, a fiatal konzervatív politikus sikerei mélységesen feldühítették az idősödő Mariust, aki a Bocchus által Sullának adományozott, Jugurtha megadását ábrázoló szobrot erővel akarta ledönteni. Nyílt szakításra azonban nem került sor a Kr. e. 91-ben kitörő itáliai szövetséges háború miatt.

Mindkét hadvezér számára új alkalom adódott a bizonyításra, amellett a köztársaságot létében fenyegető veszély egy időre feledtette a személyes sérelmeket. A hatvenhetedik évét taposó Marius Publius Rutilius Lupus consul legatusaként kezdett harcolni északon, majd annak eleste után maga vette át a hadak irányítását.
Két egymást követő csatában a legveszélyesebb ellenféllel, a Quintus Pompaedius Silo vezette marsusokkal sikerült leszámolnia, de korára és gyengeségére hivatkozva a két fontos győzelmet követően visszatért a fővárosba.

A hazatérő Marius kétségkívül jelentős sikereit azonban elhalványították a fiatalabb, energikus Sulla látványos, gyors sikerei a déli hadszíntéren. Hiába várta hát az újabb dicsőségekre vágyó agg vezér, hogy rábízzák az időközben valóban Rómára támadó Mithridatész elleni hadjáratot, hiába gyakorlatozott a Campus Martiuson a fiatalokkal minden nap, bizonyítandó jó kondícióját: Kr. e. 88 consulja Sulla lett, aki egyúttal megkapta a keleti háború vezetésének jogát. Marius ezt már nem viselhette el, és tomboló féltékenysége véres polgárháborúba taszította Rómát.