Хотя память о подвигах Мария омрачалась длинной цепью совершенных им низостей, все же теперь, когда жизни спасителя отечества угрожала опасность, в нем снова видели победителя при Верцеллах. Вся Италия, затаив дыхание, следила за эпизодами его удивительного бегства. В Остии он сел на корабль и отплыл в Африку. Но противные ветры и недостаток съестных припасов заставили его высадиться у Цирцейского мыса и скитаться наудачу, не смея довериться ничьему гостеприимству и нередко страдая от голода. Пешком в сопровождении лишь нескольких друзей престарелый Марий пришел в окрестности римской колонии Минтурн у устья Гарильяно. Вдали показались преследовавшие его всадники. С большим трудом Марий добрался до морского берега и спасся на находившемся там торговом судне. Но трусливые корабельщики причалили к берегу, и пока Марий спал на берегу, уплыли в море. Преследователи настигли Мария близ Минтурн в прибрежном болоте; он по пояс увяз в тине и спрятал голову в тростнике. Марий был доставлен минтурнским городским властям и посажен в тюрьму. Городской палач, кимврский раб, получил приказание умертвить пленника. Но германец испугался грозного взгляда того, кто некогда победил его народ: секира выпала из его рук, когда Марий прикрикнул на него своим громовым голосом, посмеет ли он убить Гая Мария. Узнав об этом, минтурнские власти устыдились, что раб, которого Марий лишил свободы, больше почитает спасителя Рима, чем сограждане, которых он спас от рабства. Мария освободили из тюрьмы, дали ему корабль и денег и отправили в Энарию (Исхию). Изгнанники, за исключением Сульпиция, собрались мало-помалу в этих водах. Они пытались высадиться у мыса Эрикса и там, где раньше стоял Карфаген, но римские должностные лица не допустили их высадки ни в Сицилии, ни в Африке. Тогда они отправились в Нумидию и на ее пустынных песчаных берегах нашли приют на зиму. Царь Гиемпсал II, у которого они рассчитывали найти поддержку, некоторое время делал вид, что готов войти с ними в соглашение. Но, внушив изгнанникам доверие к себе, он пытался захватить их в плен. С величайшим трудом беглецам удалось ускользнуть от его наездников и найти временное убежище на небольшом острове Керкине (Керкена) у берегов Туниса. Мы не знаем, благодарил ли Сулла свою счастливую звезду за то, что ему не суждено было стать убийцей победителя кимвров. Во всяком случае, минтурнские власти, по-видимому, не были подвергнуты наказанию.
Для устранения существующей неурядицы и предотвращения переворотов в будущем Сулла провел ряд законодательных мероприятий. Для облегчения положения должников, кажется, не было сделано ничего, кроме более строгого применения правил о максимальном размере процентов70. Кроме того, было постановлено организовать ряд колоний. Состав сената, очень уменьшившийся в результате сражений и судебных преследований во время союзнической войны, был пополнен тремястами новых сенаторов, подобранных, конечно, в интересах оптиматов. Наконец, были введены существенные изменения, касающиеся порядка выборов и законодательной инициативы. Старые Сервиевы правила о порядке голосования в центуриатных комициях обеспечивали почти половину всех голосов за гражданами первого цензового класса, владевшими имуществом от 100 000 сестерций и выше. Постановления 513 г. [241 г.] несколько уменьшили это исключительное преобладание первого цензового разряда. Теперь эти постановления были отменены и восстановлен старый Сервиев порядок голосования. Фактически это устанавливало ценз для выборов в консулы, преторы и цензоры: люди незажиточные по существу были лишены активного избирательного права. Законодательная инициатива трибунов была ограничена: все их предложения должны были сначала представляться сенату и лишь после его одобрения поступали на решение народа.