После триумфа, которого он в январе 104 г. до н. э. удостоился в честь победы над Югуртой, Марий не стал долго задерживаться в Риме. С момента разгрома под Араузионом прошло всего несколько месяцев, и хотя кимвры ушли дальше на запад, гарантировать, что они не вернутся, не мог никто. Но просто так ринуться на север и принять командование легионами Марий не решался, по той простой причине, что
Ее костяком должен был стать резервный легион, набранный годом ранее консулом Публием Рутилием Руфом. Когда его злосчастный коллега Маллий отправился воевать с кимврами, он остался в Риме и дальше набирать подкрепление. А теперь, не желая, чтобы это войско сидело сложа руки, занимал их подготовкой по образу и подобию гладиаторских школ. Они тренировались в рукопашном бою, занимались гимнастикой и другими физическими упражнениями. Унаследовав в начале 104 г. до н. э. эту компактную силу, Марий понял, что в его распоряжении оказалось одно из самых подготовленных подразделений из всех, которыми он когда-либо командовал.
Чтобы нарастить этот костяк свежими силами, Марий приступил к вербовке новых рекрутов. Как и в случае с Нумидийской кампанией, он добился временной отмены имущественного ценза, чтобы набирать представителей любых сословий, независимо от их происхождения. И те, кто видел, как их друзья и соседи добыли себе в Северной Африке славу и богатство, теперь тоже жаждали взяться за дело. Если раньше потерявшие надежду низшие сословия оставались в стороне от завоевания Римом Средиземноморья, то теперь выходцы из них намеревались, наряду со знатью, извлечь из войны для себя выгоду. Мы не можем точно сказать, сколько человек Марий взял с собой в Галлию, но полагаем, что армия состояла из тридцати тысяч римлян плюс сорок тысяч итальянских союзников и чужеземных вспомогательных сил. С уверенностью можно было утверждать одно – Марий позаботился о том, чтобы рядом с ним был и Сулла. Да, его раздражало, что тот присвоил себе все заслуги в поимке Югурты, но он не мог отрицать, что его помощник – один из талантливейших офицеров Рима. После годового пребывания на посту квестора, Сулла присоединился к Марию в качестве легата и стал его первым заместителем в грядущей военной кампании в Галлии.
По прибытии на место Марий миновал приграничный город Аквы Секстиевы, главную римскую базу, двинулся дальше на запад и построил на Роне, вероятно в районе нынешнего Арля, укрепленный лагерь. Если кимвры решат вернуться из Испании вдоль южного побережья или же спустятся по долине Роны, другого пути, кроме как мимо армии Мария, у них попросту не будет. Устроившись на новом месте, Марий приступил к подготовке легионов, расширив программу, реализацию которой за год до этого начал Рутилий. И хотя эта подготовка была объявлена срочной, возвращения кимвров пришлось ждать целых два года. Но даже с учетом этой передышки республика не могла насладиться мгновениями мира: хотя на северных границах царил покой, в Сицилии вспыхнуло новое кровопролитное восстание рабов.
После того, как в 130 г. до н. э. на Сицилии разразился крупный мятеж рабов, прошло тридцать лет. Когда армии «царя Антиоха» наконец были разгромлены, сенат, стараясь смягчить самые жестокие злоупотребления в отношении рабов, провел ряд реформ. Но с течением лет воспоминания о Первом восстании рабов постепенно сглаживались из памяти, и большинство римлян, владевших этой дармовой рабочей силой, постепенно вернулись к своим старым, бесчеловечным привычкам. Однако следующее восстание стало не просто реакцией на жестокое обращение; помимо прочего, в его основу легло невыполненное обещание, которое дал тот же самый Марий.
Укомплектовав свою новую армию, консул обратился к чужеземным союзникам. Но царь Никомед III из соседней Вифинии, дружественной Риму, ответил, что не может выполнить взятые на себя обязательства, сославшись на то, что сборщики податей из числа публиканов арестовывают его подданных и продают их в рабство. Аналогичные жалобы поступали и с других итальянских территорий, расположенных ближе к Риму. Купившие право собирать подати публиканы явно хватали и порабощали всех, кто не мог заплатить положенную сумму. А поскольку подобная практика подрывала способность Рима набирать легионы, сенат принял постановление, впредь запрещавшее обращать в рабство в римских провинциях граждан любых народов-союзников как в Италии, так и за ее пределами. Затем последовало еще одно решение, предписывавшее немедленно освободить всех мужчин, женщин и детей, подпадавших под эту категорию и порабощенных раньше. По иронии судьбы, именно это второе постановление и стало движущей силой второго крупного восстания рабов в римской истории.