Как военачальник Сулла прославился в ходе Югуртинской войны 111-105 годов до н.э. Тогда Рим вёл борьбу против Югурты, племянника умершего нумидийского царя Миципса, который в борьбе за трон убил двух его сыновей-наследников. Югурта стал правителем Нумидии вопреки решению римского сената. К тому же его воины при захвате в 113 году до н.э. города Цирта перебили там все население, среди которого оказалось много римских граждан.
Югуртинская война для Рима началась неудачно — царь Югурта нанёс позорное поражение римской армии под командованием Авла Постумия. В Нумидию был послан новый полководец — Квинт Цецилий Метелл, но война затягивалась, поскольку нумидийцы перешли к партизанской войне. Римский сенат назначил нового командующего армией — Гая Мария. Он, выходец из незнатной семьи провинции Лация, был избран в 107 году до н.э. консулом.
Однако и Гаю Марию не удалось одержать быструю победу. Только через два года, в 105-м, он смог вытеснить Югурту с его воинами во владения его тестя, царя Мавритании Бокха. Здесь и отличился римский военачальник — квестор Луций Корнелий Сулла. Он сумел побудить мавританского царя выдать ему своего зятя — нумидийского полководца Югурту.
Это сильно ударило по самолюбию Гая Мария, поскольку победа в Югуртинской войне стала приписываться Сулле. Тому пришлось пойти на сближение с врагами Мария, возглавляемыми родом Метеллов. И всё же поступок Луция Корнелия Суллы не смог серьёзно поколебать авторитет Гая Мария — по возвращении в Рим в январе 104 года до н.э. ему был устроен триумфальный приём. Пленённого царя Югурту провели по улицам Вечного города, после чего его задушили в тюрьме. Часть Нумидии стала римской провинцией. И всё же Сулла оказался одним из главных героев той победоносной войны.
В 104-102 годах до н.э. Луций Корнелий Сулла участвовал в войне с германскими племенами — тевтонов и кимвров, появившимися ещё в 113 году до н.э. на северо-востоке Италии. После поражения римской армии в битве с германцами при Арауозине её новым главнокомандующим сенат назначил Гая Мария. В 102 году до н.э. в битве при Аквах Секстиевых он разбил сперва войско тевтонов, а на следующий год при Верцеллах — кимвров. Остатки этих племён германцев были проданы в рабство. Война против тевтонов и кимвров добавила Сулле воинской славы. Он стал популярным военачальником среди римских легионеров.
В 90-х годах до н.э. на восточной границе Древнего Рима в Малой Азии усиливается Понтийское царство. Его правитель Митридат VI Евпатор открыто бросает вызов могущественному Риму. Римский сенат решает послать в Грецию войска под командованием Луция Корнелия Суллы, который был выборным консулом 88 года до н.э.
В это время на политической сцене вновь появляется Гай Марий, который желает возглавить восточный поход. Он начинает бороться за должность главного полководца Рима с помощью народного трибуна Сульпиция Руфа, который вносит на рассмотрение сената ряд соответствующих законопроектов. Опираясь на ветеранов легионов Мария и часть римской аристократии, Сульпиций добивается принятия предложенных им законов.
После этих событий в Вечном городе консул Сулла бежал к стоявшей возле города Нолы римской армии, отправлявшейся в поход против понтийского царя Митридата, и поднял легионы против Рима. Впервые римская армия выступила против собственной столицы. Город был взят легионерами, Сульпиций убит, а Гай Марий со своими ближайшими сторонниками, объявленными вне закона, бежал из Италии.
Луций Корнелий Сулла оказался победителем: он отменил законы Сульпиция и во главе римской армии поспешил на Восток. В 87 году до н.э. в Риме состоялись очередные ежегодные выборы консулов. Консулами стали приверженец Суллы Октавий и его противник Цинна.
Пока Сулла воевал на Востоке, власть в Риме захватили его враги Гай Марий и Цинна, которые в 86 году до н.э. были избраны консулами. Когда беглецы-марианцы возвратились в Рим, они устроили там страшную резню своих противников. Особенно свирепствовал отряд рабов, нанятый Марием, и Цинна был вынужден приказать перебить весь этот отряд рабов.
Полководец Луций Корнелий Сулла успешно воевал во время Первой Митридатовой войны. В середине 87 года до н.э. он высадился в Греции и осадил Афины, вставшие на сторону понтийского царя. К весне 86 года до н.э. город был взят и отдан на разграбление легионерам. Однако Сулла приказал прекратить разграбление Афин, сказав, что «милует живых ради мёртвых». Опустошив сокровищницы греческих храмов, полководец Рима заявил, что храмы не должны ни в чём нуждаться, так как боги наполняют их казну.
Когда армия понтийского царя Митридата Евпатора вступила на территорию Греции, римская армия под командованием Луция Корнелия Суллы разбила её в двух больших сражениях — при Херонее и Орхомене. Римляне вновь полностью овладели Грецией, попытавшейся освободиться от их владычества, и в августе 85 года до н.э. царь Понта подписал с Римом мир, признав своё поражение.
После победы в войне на Востоке Луций Корнелий Сулла начал готовиться к борьбе за власть в самом Вечном городе. Первым делом он привлёк на свою сторону армию демократов-марианцев, оказавшуюся в Греции, в Пергаме. Это удалось сделать без боя, и командовавший войсками Мария в Греции квестор Гай Флавий Фимбрий покончил жизнь самоубийством. После этого Сулла решился начать гражданскую войну в Риме.
Весной 83 года до н.э. Сулла во главе 40-тысячной армии, состоявшей из преданных ему легионеров, высадился в Брундизиуме. Гай Марий мобилизовал более 100 тысяч своих сторонников прежде всего из числа римского плебса, на сторону марианцев встали самниты — жители области Самний. В Вечном городе марианцы начали формировать новые легионы.
Однако и у Луция Корнелия Суллы в Италии оказалось немало сторонников из числа противников Гая Мария, особенно среди аристократов и военных. На его сторону встали римские войска, которыми командовали Метелл Пий и Гней Помпей. Из Северной Африки прибыл многотысячный отряд во главе с Марком Лицинием Крассом. В отличие от новых легионов марианцев, это были хорошо обученные и дисциплинированные войска, имевшие большой военный опыт.
В 83 году до н.э. у горы Тифата близ города Капуи произошло крупное сражение между войсками Суллы и марианцами. Легионы сулланцев разгромили армию консула Кая Норбана. Марианцы были вынуждены укрыться от победителей за крепостными стенами Капуи. Преследователи не решились штурмовать город во избежание больших потерь.
В следующем 82-м году до н.э. во главе войск марианцев встали опытные полководцы — сын Гая Мария Марий Младший и вновь Кай Норбан. В сражениях между сулланцами и марианцами победы одержали первые, поскольку боевая выучка и дисциплинированность легионов Суллы была на голову выше их противников.
Одна из битв состоялась у Фавенции. Здесь сразились консульская армия под командованием Норбана и армия Суллы, которой в день битвы командовал Метелл Пий. Римский консул Кай Норбан самонадеянно атаковал противника первым, но армия марианцев, измотанная длительным маршем и не успевшая перед сражением отдохнуть, была полностью разгромлена легионами сулланцев. После бегства от Фавенции под командованием консула Норбана осталась лишь 1 тысяча человек.
С другим римским консулом — Сципионом и его войсками мудрый Сулла поступил совсем иначе. Он нашёл ключ к Сципиону и большими посулами склонил его на свою сторону.
Другое сражение состоялось вблизи Сакрипонта. Здесь легионам под командованием самого Луция Корнелия Суллы противостояла 40-тысячная армия Мария Младшего. Битва была недолгой. Легионеры-ветераны Суллы сломили сопротивление плохо обученных новобранцев Гая Мария и обратили их в бегство. Больше половины из них были убиты или попали в плен к сулланцам.
Ещё одним из итогов победного для Суллы сражения при Сакрипонте стало бегство марианского полководца Кая Норбана в Северную Африку. Марий Младший с остатками своих легионов укрылся за стенами города Пренесте. Вскоре эта крепость была взята сулланцами приступом, и Марий Младший, чтобы избежать позорного и гибельного плена, покончил с собой.