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

Пострадал и Цезарь: его сместили с должности фламина Юпитера. Впрочем, он, вероятно, не сокрушался по этому поводу, но понимал в то же время, что его жизни угрожает нешуточная опасность: ведь он — племянник Мария и зять Цинны. Однако Сулла поначалу отнесся к нему более или менее снисходительно. Он только повелел Цезарю развестись с Корнелией, дочерью Цинны. Подобное повеление Сулла отдал и своим сторонникам (включая Помпея), жены которых состояли в родстве с его политическими противниками. Все подчинились, за исключением Цезаря, который заявил о своем отказе повиноваться, глядя Сулле в глаза. Трудно сказать, что двигало Цезарем: упрямство, смелость или любовь; суть не в этом, а в том, что он не подчинился диктатору. Цезаря тут же включили в список обреченных на смерть.

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

Цезарь возвратился к Корнелии, но вскоре все же решил уехать из Рима, где безраздельно властвовал Сулла, и поступить на военную службу. Приняв это решение, он направился к Марку Терму, претору римской провинции Азия, который в то время осаждал Митилену, город на Лесбосе, последний оплот мятежников, поднявших восстание против Рима по подстрекательству Митридата. Терм направил Цезаря в Вифинию, царство на северо-западе Малой Азии, чтобы привести флот, необходимый для штурма города. Вифиния была союзником Рима, и ее царь Никомед был обязан предоставлять Риму посильную военную помощь. Цезарь справился с поручением без видимых затруднений (хотя Никомед обычно неохотно взаимодействовал с Римом), что послужило распространению слухов о том, что Цезарь стал на время возлюбленным Никомеда. Цезарь эти слухи неустанно опровергал, но они преследовали его всю жизнь.

На гомосексуализм в те времена смотрели иначе, чем в наше время. Ни греки, ни римляне не заостряли вопроса о том, кто с кем разделяет ложе. Гомосексуализм не осуждался, позором считалось оказаться в положении того, кого «пользуют». Римляне даже покупали рабов для любовных утех; главным считалось не трезвонить об этом. Однако для свободного человека становиться объектом гомосексуального посягательства считалось недопустимым. Впоследствии политические противники Цезаря реанимировали слухи о его постыдной связи с царем Никомедом. Наконец во время галльского триумфа солдаты Цезаря, шагая за колесницей, среди других насмешливых песенок распевали и такую, получившую широкую известность:

Недоброжелатели Цезаря называли его «вифинейской царицей», а Никомеда нарекли прозвищем «paedicator», подразумевая, что Цезарь находился в буквальном смысле под ним. Цезарь клятвенно отвергал постыдное обвинение, но это вызывало лишь новые насмешки и зубоскальство. Чем занимался Цезарь за закрытыми дверьми с Никомедом, установить невозможно, но маловероятно, что он (каковы бы ни были его сексуальные склонности) рисковал своей репутацией ради удовлетворения похоти да еще в месте, где каждый неосторожный поступок предадут гласности.

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

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

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