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