紀元前84年にカエサルの父が死去すると、翌紀元前83年、カエサルはユピテル神官に選出される。しかし、この職務はパトリキのみに開放されており、前提としてパトリキと結婚する必要があったので、カエサルは婚約していた騎士階級（エクィテス）の娘コッスティアと別れ、コルネリウス氏族であるキンナの娘コルネリアと結婚した[24]。後にスッラはカエサルに離縁を強要したが、カエサルが拒否したため代わりに持参金を没収している[25]。ユピテル神官はローマを離れることが出来ず、戦争に関わるタブーが多かったため、もし就任していたとすれば、彼のキャリアは終わっていたはずで、実際には最高神祇官の抵抗によって就任していないと考えられる[26]。スッラのものと思われる胸像。グリュプトテーク収蔵

その頃、ミトリダテス戦争に勝利したスッラが再びローマへ進軍し、マリウス・キンナ派の抵抗を受けたがローマ市を制圧。反対派をプロスクリプティオに基づいて徹底的に粛清し、紀元前82年には従来、任期が半年に限定されていた独裁官の任期を事実上無制限とした「法制秩序再生独裁官」に就任した[27]。このスッラの帰還に合わせ、クラッススやポンペイウス、クィントゥス・カエキリウス・メテッルス・ピウスが挙兵している[28]。

血縁としてマリウスに近く、キンナの婿であるカエサルも民衆派とみなされ、彼はあやうく殺されそうになった。しかしこの時、ガイウスもしくはルキウス・アウレリウス・コッタ、マメルクス・アエミリウス・レピドゥス・リウィアヌス、ウェスタの処女らに助命嘆願され、スッラもこれにしぶしぶ同意する。その時スッラは「いいだろう。許そう。だが忘れるな。いつかあの若者が我々貴族[注釈 4]を滅ぼすぞ。彼の中には多くのマリウスがいるのだ」と語ったと伝えられる[24]。

紀元前81年、カエサルはアシア属州を担当していたプラエトル、マルクス・ミヌキウス・テルムス[29]のもとに派遣され、ビテュニア王ニコメデス4世のもとに艦隊調達の交渉に向かい長期間滞在する。スエトニウスによれば、この時に王と若いカエサルは男色関係を持ったという噂が立ったが、ミュティレネ包囲戦では「市民冠」を授与されている[30]。この市民冠の授与によって、カエサルが元老院に議席を得、その特権によって政務官の年齢制限を回避できたとすれば、紀元前100年生まれでもおかしくはないことになる[31]。ただ、この男色の噂は生涯に渡って付いて回り、「ビテュニアの女王」などと政敵より攻撃される材料となった[32]。

この頃ローマでは、コルネリウス法を制定し改革を一通り終えたスッラが紀元前80年に独裁官を辞していた。このスッラの行動を後年カエサルは、「自分から独裁官を辞めるようなおめでたい奴をスッラと呼ぶのさ」と評したという[33]。
スッラ死後

紀元前78年にスッラが死去したことでカエサルはローマへ帰還した。すると、同僚執政官と反目し、スッラが定めた護民官権限削減の復活や穀物法の撤回、没収された資産の返却などを訴え挙兵したマルクス・アエミリウス・レピドゥス[34]はカエサルに参加を呼び掛けたが、カエサルはこれを断った[35]。

当時ローマでは属州統治に現地民への脅迫や搾取・収賄を行う者が頻繁にいた。紀元前77年、カエサルは執政官経験者のグナエウス・コルネリウス・ドラベッラをこの罪で訴追した[36]。共和政ローマでは私人訴追主義で、訴追者自らが裁判で相手側弁護士と戦うため、多数決で判決を下す審判人を説得するための高度な修辞学が求められ、訴追者は政敵や訴追によって名を売ろうとする若者、職業的訴追人などが主であった[37]。

このドラベッラの告発に失敗し、復讐を恐れたカエサルは紀元前75年にロドス島へ赴き、キケロの師で[38] 修辞学の権威として著名であったアポロニウス・モロンに師事した[39]。彼には弁舌の才能もあったが、その努力を政治や軍事方面に向けた結果覇者となったため、キケロは他の雄弁家と比較することは避けたという[40]

この時カエサルはエーゲ海を船で渡っていたが、途中キリキアの海賊に囚われの身となった。海賊は身代金として20タレントを要求したが、カエサルは「20では安すぎる、50タレントを要求しろ」と海賊に言い放ち、その間海賊に対して恐れもせずに尊大に接するだけではなく、「自分が戻ったらお前たちを磔にしてやるぞ」と海賊に対し冗談すら言った。そして身代金が支払われて釈放されるとカエサルは海軍を招集し海賊を追跡、捕らえてペルガモンの獄につないだ。そしてアシア属州の総督に処刑するように命じるが、総督はこれを拒否して海賊を奴隷に売ろうとする。するとカエサルは海路を引き返して、冗談でほのめかした通りに自分の命令で海賊たちを磔刑に処したという[41]。

紀元前73年、カエサルは死去したガイウス・アウレリウス・コッタ (紀元前75年の執政官)の後継神祇官に就任したと考えられている[42]。
クルスス・ホノルム

紀元前71年、軍団司令官（トリブヌス・ミリトゥム）に就任[43]、クルスス・ホノルムを歩み始めた。ヒスパニアでのクィントゥス・セルトリウスによるローマとの戦争（英語版）に加えて、紀元前73年にはスパルタクスらが首謀した第三次奴隷戦争が勃発、グナエウス・ポンペイウスやマルクス・リキニウス・クラッススがこれらの戦争で活躍していた。