Caesar se však nevrátil do Říma, místo toho se připojil k vojsku v Asii.Během obléhání města Mytilén byl Caesar vyslán do Bithýnie, aby požádal místního krále Nikoméda o podporu jeho flotily.Při závěrečném útoku na Mytilény si Caesar počínal natolik udatně a odvážně, že si zasloužil občanskou korunu.Toto vyznamenání náleželo tomu Římanovi, který v bitvě zachránil život spoluobčanovi.Krátce se zúčastnil rovněž tažení proti pirátům Kilíkii.
Po dvou letech samovlády se Sulla vzdal úřadu diktátora a obnovil republikánské uspořádání.Dokonce propustil i své liktory a zcela nestřežen se procházel po fóru.O dva roky potom zemřel a byl mu vystrojen státní pohřeb.Když se Caesar v roce 78př.n.l. doslechl o Sullově smrti, cítil, že už nic nebrání jeho bezpečnému návratu do Říma.Z důvodu nedostatku prostředků si pořídil skromný domek ve čtvri Subura, již obývali méně majetní Římané.Samotný Cicero tehdejší rétor prohlásil: ,,Najde se někdo, kdo ovládá lépe než Caesar schopnost mluvit?"Aby ještě zdokonalil své řečnické umění, odcestoval Caesar v roce 75př.n.l. na Rhodos, kde studoval filozofii a rétoriku u slavného učitele Apollónia Molóna, který dříve učil i Cicera.
V průběhu plavby Egejským mořem byl však Caesar unesen kilickými piráty a následně byl jimi držen jako vězeň v oblasti Dodekanénsého moře.Když za něho piráti požadovali výkupné dvacet talentů zlata, naléhal na ně, aby si řekli o padesát.Po propuštění na svobodu schromáždil Caesar loďstvo s, kterými pronásledoval piráty a nakonec dopadl.Správce provincie Asie v Pergamenu je odmítl popravit, jak Caesar žádal, a dal přednost jejich prodeji do otroctví.Caesar se, ale pro piráty vrátil a na vlastní odpovědnost je dal ukřižovat, jak jim slíbil během svého zajetí.Poté pokračoval na Rhodos, brzy však byl odvolán zpátky do Asie.
V Římě byl zvolen vojenským tribunem a učinil tak první krok své politické kariéry.V té době zuřila v Itálii válka se Spartakem, není známo jakou, pokud vůbec nějakou, úlohu v ní Caesar sehrál.Byl zvolen quaestorem pro rok 69př.n.l. a v tomto roce pronesl smuteční řeč za svoji tetu Julii.Při smutečním procesí byly neseny zakázané Mariovy obrazy, což byla od Sullova nástupu věc vskrtku nevídaná.Jeho manželka Cornelia v témže roce.Caesar pak odešel do Hispánie.Podle Suetonia spatřil v Gadesu sochu Alexandra Velikého, přitom si prý posteskl, že dosáhl věku, kdy Alexandrovi už ležel u nohou celý svět, zatímco on sám dosud nic nedokázal.Po návratu z Hispánie se oženil s Pompejou, Sullovou vnučkou.Po zvolení aedilem nechal obnovit pomníky Mariových vítězství - šlo o velice kontroverzní čin, neboť moc v Římě stále drželi někdejší Sullovi straníci.Rovněž vznesl několik žalob proti občanům, kteří se obhatili na majetku proskribovaných a vynaložil velkou část peněz půjčených převážně od Marca Crassa na veřejné práci a hry, čímž zastínil svého kolegu v úřadě Marca Calpurnia Bibula.