Вернувшись к Минуцию Терму, Цезарь принял участие во взятии Митилен, отличился при штурме и за проявленную храбрость был награжден дубовым венком. В 78 г. он переехал в Киликию, где участвовал в военных действиях, которые вел здесь проконсул Публий Сервилий Ватия (кстати, бывший сулланец) против морских разбойников. Однако в Киликии Цезарь задержался ненадолго. Вскоре сюда дошла весть о смерти Суллы, и он поспешил вернуться в Рим.
Непрочность и непопулярность сулланского режима стали ясны сразу же после смерти его создателя. Консул 78 г. М. Эмилий Лепид, бывший сулланец, наживший на проскрипциях немалое состояние, выступил теперь с требованием пересмотра ряда установлений покойного диктатора. В частности, он обещал вернуть земельные участки, конфискованные Суллой, их законным владельцам. Дело дошло до того, что Лепид двинул набранное им войско на Рим, но потерпел поражение, бежал в Сардинию, где вскоре и умер .
В начале этих событий в Рим возвратился Цезарь, и, если верить Светонию, Лепид пытался завербовать его в число своих приверженцев и «прельщал крупными выгодами» . Однако, несмотря на рано проявившуюся склонность и даже вкус к политическим интригам, молодой Цезарь обнаружил на первых порах большую осмотрительность и не дал вовлечь себя в предприятие, почти не имевшее шансов на успех. Он остался в стороне и от другого, гораздо более серьезного движения, возглавленного одним из крупнейших вождей марианской оппозиции — Квинтом Серторием. И хотя военные действия во время этой так называемой Серторианской войны происходили на территории Испании, но еще Сулла, а затем и сенат рассматривали это движение как непосредственную угрозу, бросив на его подавление крупные силы под командованием молодого, но успевшего уже прославить себя полководца — Помпея .
Не приняв — и, видимо, вполне сознательно — участия в этих экстремистских выступлениях, Цезарь избрал совсем иную форму для своего политического дебюта. Он предпочел наименее опасный и ь то же время широко используемый в Риме путь к достижению определенной политической репутации и карьеры: активное участие или, вернее, инициативу в организации громких судебных процессов, причем по возможности процессов с политической окраской.
В 77 г. он обвинил в вымогательствах и привлек к суду видного сулланца Г. Корнелия Долабеллу, который был консулом 81 г., а затем управлял Македонией. И хотя благодаря защите Г. Аврелия Котты и Кв. Гортензия, опытнейших судебных ораторов и патронов, Долабелла был оправдан, но обвинительная речь Цезаря оказалась настолько блестящей, что сразу утвердила за ним репутацию одного из первых ораторов Рима. О популярности этой речи свидетельствует тот факт, что она ходила в списках и сохранялась по крайней мере до II в. н. э. (поскольку была известна Тациту и Авлу Геллию ). В следующем 76 г. Цезарь по просьбе греков привлек к суду за вымогательства и взяточничество Гая Антония, тоже сулланца, который, будучи командиром конницы во время войны с Митридатом, приобрел в Греции скандальную славу. Антонию, однако, удалось избежать суда, поскольку он обратился за помощью и защитой к народным трибунам .
После этих двух процессов, не принесших ему удачи, но и не повредивших его репутации, Цезарь снова покидает Рим и отправляется на Родос слушать лекции знаменитого ритора Аполлония Молона (за несколько лет до этого у него совершенствовался в ораторском искусстве сам Цицерон). Когда Цезарь возвращался с Родоса, то у острова Фармакусса он был захвачен в плен пиратами. Оба биографа Цезаря — и Светоний и Плутарх — весьма живописно излагают этот эпизод. Версия Светония скромнее: Цезарь пробыл в плену около сорока дней, большинство своих спутников он разослал по малоазиатским городам на предмет сбора необходимой суммы для его выкупа. Выплатив пиратам 50 талантов (или 300 тысяч денариев). Цезарь был освобожден, но на этом не успокоился: собрав флот, он погнался за пиратами, захватил их и предал казни, как шутя обещал им во время своего плена .
Версия Плутарха более цветиста и потому менее правдоподобна. Плутарх вообще излагает события жизни Цезаря за 81 — 73 гг. в несколько иной последовательности, Согласно его версии, Цезарь уезжал из Рима лишь один раз. Он скрывается от преследований Суллы в Вифинии у Никомеда, затем попадает в плен к пиратам, после этого живет на Родосе и, наконец, узнав о смерти Суллы, возвращается в Рим. Что касается пребывания Цезаря у пиратов, то рассказ изукрашен такими яркими, но едва ли правдоподобными деталями: пираты якобы запросили с Цезаря 20 талантов, а он сам увеличил сумму выкупа до 50 талантов; кроме того, во время своего пребывания а плену он заставлял пиратов слушать декламируемые им стихи и речи его собственного сочинения и запрещал шуметь, когда ложился отдыхать. Нагнав и захватив пиратов после своего освобождения, он всех их приказал распять .