В Риме тотчас после смерти Суллы консул М. Лепид сделал попытку свергнуть учрежденное Суллой правительство и уничтожить силу его партии. Он предложил Цезарю соединиться с ним. Но Цезарь знал, что могущество партии Суллы очень крепко для того, чтобы быть уничтоженным Лепидом, который предпринял это дело без достаточной подготовки; потому он уклонился от участия в этом предприятии. Слишком поспешный план Лепида потерпел полную неудачу. Тогда Цезарь удовлетворился тем, что привлек к суду за притеснение отдельных выдающихся личностей из приверженцев Суллы – Кн. Корнелия Додабеллу и К. Антония – и этим достиг двоякой цели: выказал свой отличный ораторский талант и желание добра народу и возбудил недовольство тогдашним правительством, так как сенаторский суд отказался от осуждения обвиняемых. Чтобы укрыться от ненависти сильных противников, он отправился зимой 76 г. на остров Родос, где хотел усовершенствоваться в ораторском искусстве под руководством знаменитого ритора Молона. Во время своего путешествия недалеко от Милета, близ острова Фармакузы, он был взят в плен морскими разбойниками. Рассказывают, что в продолжение 38 или 40 дней, проведенных им против воли на пиратском корабле, он считал себя вовсе не пленником, а господином пиратов; когда ему хотелось спать, он приказывал им соблюдать тишину; когда они недостаточно хвалили его стихи и речи, которые он читал им для препровождения времени, он шутя бранил их, называя грубыми варварами, и грозил, что велит всех их распять. Они потребовали с него 20 талантов выкупа, а он, говорят, обещал им 50, потому что за такого человека, как он, 20 талантов было бы слишком мало. Когда жители Милета доставили выкуп и Цезарь был высажен на берег, он в следующую же ночь собрал несколько милетских кораблей, захватил пиратов при Фармакузе и велел распять их в Пергаме, как говорил им раньше. На Родосе Цезарь пробыл недолго; когда в 74 г. началась третья война с Митридатом, он поспешил в провинцию Азию, собрал, как частный человек, войско и обратил в бегство неприятеля, явившегося сюда затем, чтобы взбунтовать города против Рима. В это время он был заочно избран понтифексом, на место своего умершего дяди К. Аврелия Котты. Поэтому он поехал опять в Рим, не без страха перед пиратами, от которых он, в крайнем случае, решил избавиться самоубийством.
В последующие годы Цезарь мало участвовал в общественных делах, но зато старался приобрести расположение народа ласковым обращением и щедрой раздачей денег и хлеба. Оптиматы с завистью видели, что влияние их молодого противника с каждым днем возрастает, но утешались надеждой, что с растратой имущества он утратит и свое влияние. Но Цезарь, нисколько не беспокоясь, делал долги за долгами, в твердой уверенности, что расположение народа поможет ему достигнуть должностей, в которых он снова будет в состоянии поправить свои расстроенные дела. Когда Помпей возвратился из Испании после войны с Серторием, Цезарь был уже влиятельнейшим главой народной партии и делал все возможное, чтобы привлечь на сторону народа этого высокопоставленного человека, который был в разладе с сенатской партией, и окончательно поссорить его с оптиматами. Его план состоял в том, чтобы при помощи Помпея уничтожить преобладание сенатской партии, а впоследствии, когда он, благодаря союзу с Помпеем, поднимется высоко, самому пожать плоды этого союза, так как он надеялся, что Помпей, не способный поддерживать свои отношения с народом, никогда не будет иметь в народе твердой почвы. Помпей охотно принял услуги ловкого и умного народного вождя и с гордой уверенностью не опасался, что Цезарь станет работать только для себя самого. Когда он во время своего консульства в 70 г. уничтожил конституцию Суллы, Цезарь, душа всего этого дела, стоял на заднем плане.
В 68 г. Цезарь стал квестором – должность, открывавшая собой путь к курульной карьере. В этом году умерли сестра его отца, старая Юлия, вдова Мария, и его собственная супруга Корнелия, дочь Цинны. Потеря жены была для него прискорбна, но он воспользовался смертью ее, как и Юлии, чтобы воззвать к тени старых вождей народа, Мария и Цинны, и возбудить надежды демократии. Он сказал обеим женщинам надгробные речи на форуме, что было неслыханным делом по отношению к столь молодой женщине, как Корнелия, но эти надгробные речи были скорее похвальными речами Марию и Цинне и их принципам. Кроме того, на похоронах Юлии несли изображение Мария, несмотря на то, что над ним тяготела опала. Оптиматы были раздражены, но народ радостно одобрил Цезаря и признал в нем человека, призванного возвратить старые времена народного господства.
После этого Цезарь в качестве квестора сопровождал претора Антистия Вета в Ближнюю Испанию, где, по почетному предложению своего начальника, весьма правдиво и деятельно отправлял правосудие в одной части страны.