Цезарь возвратился к Корнелии, но вскоре все же решил уехать из Рима, где безраздельно властвовал Сулла, и поступить на военную службу. Приняв это решение, он направился к Марку Терму, претору римской провинции Азия, который в то время осаждал Митилену, город на Лесбосе, последний оплот мятежников, поднявших восстание против Рима по подстрекательству Митридата. Терм направил Цезаря в Вифинию, царство на северо-западе Малой Азии, чтобы привести флот, необходимый для штурма города. Вифиния была союзником Рима, и ее царь Никомед был обязан предоставлять Риму посильную военную помощь. Цезарь справился с поручением без видимых затруднений (хотя Никомед обычно неохотно взаимодействовал с Римом), что послужило распространению слухов о том, что Цезарь стал на время возлюбленным Никомеда. Цезарь эти слухи неустанно опровергал, но они преследовали его всю жизнь.
На гомосексуализм в те времена смотрели иначе, чем в наше время. Ни греки, ни римляне не заостряли вопроса о том, кто с кем разделяет ложе. Гомосексуализм не осуждался, позором считалось оказаться в положении того, кого «пользуют». Римляне даже покупали рабов для любовных утех; главным считалось не трезвонить об этом. Однако для свободного человека становиться объектом гомосексуального посягательства считалось недопустимым. Впоследствии политические противники Цезаря реанимировали слухи о его постыдной связи с царем Никомедом. Наконец во время галльского триумфа солдаты Цезаря, шагая за колесницей, среди других насмешливых песенок распевали и такую, получившую широкую известность:
Галлов Цезарь покоряет, Никомед же Цезаря:
Нынче Цезарь торжествует, покоривший Галлию, —
Никомед не торжествует, покоривший Цезаря[6].
Недоброжелатели Цезаря называли его «вифинейской царицей», а Никомеда нарекли прозвищем «paedicator», подразумевая, что Цезарь находился в буквальном смысле под ним. Цезарь клятвенно отвергал постыдное обвинение, но это вызывало лишь новые насмешки и зубоскальство. Чем занимался Цезарь за закрытыми дверьми с Никомедом, установить невозможно, но маловероятно, что он (каковы бы ни были его сексуальные склонности) рисковал своей репутацией ради удовлетворения похоти да еще в месте, где каждый неосторожный поступок предадут гласности.
Возможно, чтобы пресечь постыдное обвинение, Цезарь при штурме Митилены проявил подлинную отвагу. Корабли, которые он привел Терму, были крайне необходимы при штурме города, стоявшего на берегу небольшого острова. Несмотря на отчаянное сопротивление защитников Митилены, римляне взяли город, причем Цезарь сражался в первых рядах. Его личная храбрость и пренебрежение смертельной опасностью станут его отличительными особенностями, где бы в дальнейшем он ни сражался — и в Галлии, и в Британии, и в Египте. Даже когда он стал правителем Рима и мог бы себя поберечь без ущерба для своей репутации, Цезарь на поле брани находился в первых рядах и вел за собой солдат. При взятии Митилены Цезарь получил за свое геройство дубовый венок. Когда он появился в этом венке на празднестве в Риме, все присутствовавшие, включая сенаторов, встали со своих мест в знак признания его несомненных заслуг. Эта слава помогла Цезарю в его политической и военной карьере.
После взятия Митилены Цезарь некоторое время служил в Киликии, римской провинции в Малой Азии, под началом проконсула Сервилия Исаврика. Киликия, чье средиземноморское побережье было изрезано многочисленными скрытыми от неосведомленных глаз бухточками, служила пристанищем для пиратов, которые то и дело атаковали не ожидавшие нападения корабли и пленяли людей с целью выкупа. Сервилий Исаврик вел с ними борьбу, и Цезарь стал участвовать в проводившихся им боевых операциях по уничтожению дерзких пиратов.
В 78 году в Киликии узнали о смерти Суллы, который незадолго до своего ухода из жизни неожиданно сложил с себя властные полномочия и удалился в свое поместье в Кампанию, где стал вести разгульную жизнь. Противники Суллы говорили, что он, как и пресловутый царь Ирод, был съеден живой червями.
Кончина Суллы позволила Цезарю, не опасаясь последствий, вернуться в Рим, где началась очередная борьба за власть, в которой принял участие и консул Марк Лепид, в свое время помогавший Цезарю вернуться из изгнания в Рим. Лепид оставил партию оптиматов и присоединился к движению популяров — не из убеждений, а с целью захватить власть. Лепид предложил Цезарю присоединиться к нему, посулив немалые выгоды. Однако Цезарь, хотя и был в душе популяром, отклонил предложение — его разочаровал как сам вождь, так и задуманное им предприятие. Чутье не подвело Цезаря: заговор Лепида окончился неудачей.