Перед тем как Цезарь женился и стал фламином, он официально вступил во взрослую жизнь, получив права гражданина, что сопроводилось облачением в toga virilis (тогу, которую носили юноши с 16 лет). В этом году умер его отец, и Цезарь стал главой дома.
Тем временем Сулла воевал на Востоке с Митридатом VI. В 87 году Сулла вторгся со своим войском в Грецию и год спустя взял Афины. Затем он направился в Македонию, после чего, переправившись через Босфор, вступил в Малую Азию. Митридат вскоре уразумел, что следует смириться с потерями, и заключил с Суллой мир, подписанный в местечке близ Трои. Митридат согласился больше не притязать на римские территории, передать свой флот Сулле и выплатить солидную контрибуцию. Впоследствии Рим признал права Митридата на Понтийское царство, которое стало его союзником. Сулла мог бы окончательно разгромить войска Митридата и захватить его земли, но при этом и его собственные войска понесли бы значительные потери. Сулле же нужны были люди, чтобы, вернувшись в Рим, свергнуть Цинну. Поэтому он и заключил мир с Митридатом, после чего повернул войско на запад.
Организовать сопротивление Сулле Цинне не довелось. При подготовке к выступлению против возвращавшегося из Азии Суллы Цинна был убит солдатами, отказавшимися за ним следовать. В 83 году Сулла беспрепятственно высадился в Брундизии. К Сулле тут же присоединились патриции, сумевшие при Марии уцелеть или просто лишившиеся государственных должностей. Среди них оказались Марк Лициний Красс, чьи старший брат и отец стали жертвами Мария, а также Помпей, сын Помпея Страбона, который привел с собой три легиона. Семнадцатилетний Цезарь в то время, конечно, даже думать не мог, что эти двое, Красс и Помпей, будут вместе с ним управлять Римом.
Сулла беспрепятственно прошел через всю Кампанию, затем разбил одно из двух войск, выступивших против него, а второе просто переманил посулами на свою сторону. Сыну Мария удалось собрать еще одно войско, но оно было окружено у Пренесте, городка вблизи Рима. Популяры поняли, что их дело проиграно, и бежали из Рима, но перед этим устроили в городе очередную резню. Сулла взял Рим во второй раз и вскоре разбил остатки сил марианцев в Италии и Испании, после чего по существу стал полновластным правителем Рима.
Резня, которую Сулла устроил в Риме, превзошла по своим масштабам даже расправу Мария со своими политическими противниками. Сулла придумал систему истребления неугодных. В Форуме вывесили списки людей, подлежащих уничтожению, при этом, согласно системе Суллы, всякому исполнителю гарантировалось большое вознаграждение за каждого убиенного, а земли и имущество этого злосчастного человека переходили в собственность государства. Таким образом Сулла не только расправился со своими врагами, но и пополнил государственную казну. Жертвами небывалого произвола стали тысячи человек, причем погибли не только политические противники Суллы, но и просто богатые люди, далекие от политики. Сулла также издал закон, согласно которому детям попавших в злополучные списки людей запрещалось заниматься общественной деятельностью. Кроме Рима Сулла захватил италийские земли своих врагов и раздал их своим соратникам и верным солдатам. Чтобы покончить со всеми установлениями популяров и преодолеть государственный кризис в духе идей оптиматов, Сулла провозгласил себя диктатором. Он вновь передал суды в руки сенаторов, ограничил полномочия народных трибунов и тем самым лишил главной опоры плебеев и популяров. Кроме того, он наделил Северную Италию статусом римской провинции, что позволило разместить там войска на постоянной основе.
Пострадал и Цезарь: его сместили с должности фламина Юпитера. Впрочем, он, вероятно, не сокрушался по этому поводу, но понимал в то же время, что его жизни угрожает нешуточная опасность: ведь он — племянник Мария и зять Цинны. Однако Сулла поначалу отнесся к нему более или менее снисходительно. Он только повелел Цезарю развестись с Корнелией, дочерью Цинны. Подобное повеление Сулла отдал и своим сторонникам (включая Помпея), жены которых состояли в родстве с его политическими противниками. Все подчинились, за исключением Цезаря, который заявил о своем отказе повиноваться, глядя Сулле в глаза. Трудно сказать, что двигало Цезарем: упрямство, смелость или любовь; суть не в этом, а в том, что он не подчинился диктатору. Цезаря тут же включили в список обреченных на смерть.