Довольно большое число молодых аристократов, особенно тех, кто потерял родственников во время чисток Мария и Цинны, также примкнули к Сулле после его высадки на берег в Брундизии, но Помпей решил явиться к проконсулу не с пустыми руками. Двадцатитрехлетний молодой человек был очень осмотрительным и начал набирать свое войско в Пицене. Его популярность и нежелание отказывать самым богатым местным землевладельцам обеспечило ему поддержку как отдельных граждан, так и целых общин.

Доверенным лицам Карбона не удалось остановить набор рекрутов, и в итоге им пришлось бежать. Скоро Помпей сумел набрать отряд кавалерии и целый легион. Он лично назначил центурионов и разделил легион на когорты. Помпей на собственные деньги приобрел все необходимое снаряжение и выплатил жалованье легионерам. К тому же он закупил продовольствие, вьючных животных и повозки. Вскоре были набраны еще два легиона. Их оснащение проходило точно таким же образом. Все делалось очень тщательно, по существующим канонам, за исключением одного: у Помпея вообще не было права набирать какую-либо армию.

Закончив набор войска, Помпей направился на юг, чтобы присоединиться к Сулле. Несколько вражеских армий попытались помешать ему, но командовали ими бездарные полководцы, которые к тому же плохо согласовывали свои действия. Также следует помнить, что хотя Карбон и его союзники набрали огромное войско — Аппиан утверждает, что в нем было 250 когорт, — подавляющее большинство солдат были такими же новичками, как легионеры Помпея. Юному командиру угрожали три армии, каждая из которых была такой же численности, как его собственная, или даже больше. Он атаковал ближайшего противника, в войсках которого находилась вспомогательная галльская кавалерия. Молодой, назначивший сам себя полководец начал бой, лично поведя своих кавалеристов в атаку.

Определив, кто стоит во главе галльских всадников, Помпей устремился к нему и сразил его точно, так же как Марцелл когда-то убил Бритомарта. Смерть вождя посеяла панику среди галлов. Они повернули назад, приведя в замешательство остальную армию, которая в свою очередь обратилась в бегство.

Это была первая из тех побед, которые Помпей одержал перед тем, как добрался наконец до Суллы и его главной армии. Оказанный ему радушный прием превзошел все ожидания, ибо проконсул спешился, чтобы приветствовать молодого полководца, и провозгласил его императором (imperator). Такого обращения обычно удостоивался командующий, одержавший крупную победу. Помпей стал одним из старших подчиненных Суллы, и тот доверял ему больше, чем остальным. Сулла всегда вставал со своего места и обнажал голову всякий раз, когда появлялся его молодой союзник. Остальным известным людям такие почести, как правило, не оказывались.

Ни одна из сторон в этой войне не проявляла большого уважения к закону, ибо Карбон сам назначил себя консулом на 82 г. до н. э. и сделал сына Мария, которому не было еще 30 лет, своим коллегой. Весной Помпей отправился в Цизальпинскую Галлию для поддержки проконсула Метелла — одного из сторонников Суллы. С Метеллом позднее они будут вместе служить в Испании. Вдвоем они одержали несколько побед в Северной Италии, а Сулла тем временем захватил Рим.

Часть самнитских союзников Карбона сумели сначала отвлечь Суллу, а затем едва снова не захватили Город. Но проконсул вовремя вернулся и одержал победу в долгой и кровопролитной битве у Коллинских ворот. Во время боя Сулла подъехал к левому крылу, где его солдатам приходилось особенно туго, и два вражеских воина заметили его и решили убить. Сулла, пытавшийся в этот момент исправить ход сражения, не заметил угрозы, и вполне мог бы погибнуть, если бы его конюх не был начеку и не ударил плетью белого коня полководца. Животное рванулось вперед и дротики, направленные в Суллу, не достигли цели. Римский стиль командования подвергал полководца значительному риску, даже если он не участвовал непосредственно в бою.

Установив полный контроль над Римом, Сулла провозгласил себя диктатором, восстанавливающим республику (dictator republicae constituendae). Он возродил старую верховную должность, но не ограничил свою власть шестимесячным сроком. Месть Суллы своим врагам была не менее жестокой, чем расправы Мария и Цинны, но репрессии осуществлялась более организованно. Самниты, захваченные в плен в бою у Коллинских ворот, были перебиты, а для расправы над римлянами Сулла составил проскрипционные списки и вывесил их на Форуме. Люди, чьи имена были занесены в эти списки, объявлялись вне закона и сразу же лишались всех гражданских прав. Любой мог принести властям труп или отрубленную голову в качестве доказательства смерти проскрибированного, и немало этих ужасных трофеев вскоре украсили Форум и другие общественные места Рима. Значительная часть собственности убитых перешла к Сулле или в казну. Диктатор щедро распределял отвратительную добычу среди своих сторонников, и многие из них почти мгновенно разбогатели. Позднее ходило множество слухов об именах, добавленных в проскрипционные списки из личной мести или из желания поживиться чужим добром.

Среди лиц, попавших в проскрипционные списки, было много сенаторов и всадников. Связано это было как с их политической ролью, так и их богатством. Впоследствии Сулла добавил новых членов в списки сената, удвоив его прежнюю численность и доведя ее приблизительно до 600 человек.

В течение следующего года он ввел в действие закон, ограничивающий власть народных трибунов. Данный закон делал этот пост бесперспективным для амбициозных молодых людей, поскольку запрещал народным трибунам занимать в дальнейшем какие-либо государственные должности. Суды были реформированы, четко прописаны правила занятия должностей и деятельности магистратов и наместников. Программа реформ Суллы как диктатора являлась практически всесторонней. С ней могут сравниться лишь реформы Юлия Цезаря, ставшего диктатором после победы в более поздней Гражданской войне.

Тем не менее больше всего поражает то, как мало Сулла старался изменить основную природу римской республики. Несмотря на всю ту порочность, с какой римские лидеры вели друг с другом борьбу, эти конфликты редко имели под собой сколько-нибудь значительную идеологическую основу. Люди боролись за власть или чтобы не допустить ее перехода в руки ненавистного соперника. Хотя некоторые революционеры ради популярности в народе обещали раздать землю или списать долги, никто, похоже, не собирался менять основы римской республики. Главная цель любого лидера и его сторонников заключалась в смещении прежней элиты. Когда Сулла добился верховной власти, краеугольным камнем его реформ стало введение в сенат своих приверженцев.

Хотя Гражданская война в Италии была практически закончена, сторонники Мария продолжали борьбу в провинциях. Осенью 82 г. до н. э. Сулла отправил Помпея на Сицилию, при этом молодой человек в первый раз получил официальные полномочия, поскольку сенат предоставил ему пропреторский империй. Кампания не заняла много времени, так как приверженец Мария пропретор Перперна быстро сбежал. Однако удалось захватить и казнить бывшего консула Карбона. Помпея осуждали за глумление над пленником, хотя последний заслужил лишь презрение, поскольку не смог встретить казнь с мужеством, достойным римского аристократа. О молодом командующем ходили слухи, что он допускает и другие вольности — вследствие своей почти неограниченной власти, но в целом считалось, что Помпей вел себя куда более сдержанно, чем другие сторонники Суллы.