Z Atén zamieril po rímskej vojenskej ceste na sever, z Attiky cez Boiótiu a Tesáliu a priesmyk Tempé, prechádzali popri neďalekom Olympe. Potom sa plavili z ostrova na ostrov, kým nedorazili k Helespontu. Odtiaľ sa za tri dni dostali do Nikomédie. V Bitýnii a jej okolí zostal šestnásť mesiacov. Na túto idylu neskôr spomínal ako na najkrajšie obdobie až do svojim päťdesiatich troch rokov, keď sa mu začal ešte krajší život. Navštívil Tróju, Byzantium a iné historické miesta. Stretol sa aj so svojím prastrýkom z matkinej strany. Sedemdesiatdeväťročný Publius Rutilius Rufus sa narodil v tom istom roku ako Gaius Marius a už dlho žil v dobrovoľnom vyhnanstve v Smyrne. Hoci si Caesar na neho ledva spomínal, veľmi si starca obľúbil. Každá idyla sa však musí raz skončiť a Caesar sa rozhodol, keď ho v Nikomédii zastihol list z Tarsu, že sa musí ďalej venovať vojenskej službe. Bolo to v apríli toho roku, čo zomrel Sulla. Mal nastúpiť ako mladší legát u Publia Servilia Vatiu, vlaňajšieho konzula, teraz miestodržiteľa Kilikínie. Vatia mal za úlohu skoncovať s pirátmi. Koncom apríla dorazil do Tarsu. Caesar dostal za úlohu vybudovať loďstvo. V tom mal naozaj bohaté skúsenosti. Vatia potreboval obrovskú flotilu. Caesar sa pustil budovať loďstvo, ale chýbalo mu nadšenie. Bol bojachtivý, ale Vatia sa do boja nijak nehrnul. Potešilo ho aspoň to, že mohol cestovať. Rodos bol námornou mocnosťou, ktorej sa vo východnej časti Stredomoria nič nevyrovnalo, a preto sa naň Caesar v máji vybral. Caesar bol veľký diplomat, takže presvedčiť Rodos mu nerobilo problém. Rodos sľúbil lode, kapitánov a posádky, nie však vojakov. Z Rodosu sa vybral na Cyprus. Vylodil sa v Pafose, sídle cyperského vládcu Ptolemaia Cyperčana. Ako zistil, Cypru v skutočnosti vládlo dvanásť úradníkov. Preto Caesar sústredil všetku energiu na to, aby ich presvedčil. To sa mu samozrejme podarilo.
Caesar sa vrátil do Tarsu k Vatiovi a oboznámil ho s dohodami, podľa ktorých mu na požiadanie poskytnú lode a posádky zo všetkých prímorských miest a oblastí pod jeho správou. 2.2.4. Vojna medzi Catulom a Lepidom

Po Sullovej ére sa prvým konzulom stal Marcus Aemillius Lepidus, druhým bol Quintus Lutatius Catulus. Títo dvaja sa nemali príliš v láske. Lepidus chcel upraviť Sullove zákony, Catulus bol proti. Spory vyústili až do vojny. Lepidus zaútočil na Rím, Catulus ho porazil. Aj Caesar sa zapojil do bojov. Hoci bol Catulovým bratrancom, ten ho nechcel prijať do svojho štábu. A tak Caesar nastúpil do bojov ako radový vojak. Kohorta, v ktorej bol, ani nezasiahla do boja. Medzitým začali s Cinnillou manželsky žiť.