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