Jego znajomi w Rzymie, krewni Aurelii, przede wszystkim jej starszy brat, lubiany przez Sullę Aureliusz Kotta, a nawet dziewicze westalki, wstawiali się za Cezarem, aby umożliwić mu bezpieczny powrót do Rzymu. Udało im się to, mimo iż Sulla ostrzegł, że młodzieniec, za którym się wstawiają, przysporzy stronnictwu optymatów wielu trosk („strzeżcie się: w tym Cezarze drzemie wielu Mariuszów”)Swetoniusz, s. 25.. Cezar jednak nie miał zamiaru wracać do Rzymu – wiedział, że w tak niedogodnym położeniu politycznym, w jakim się znalazł, jego kariera polityczna była skazana na klęskę. Wiedział także, że jako polityk będzie musiał się wcześniej wykazać służbą w armii i walką.
Udał się do północno-zachodniej Azji Mniejszej, gdzie wspomagał Marka Minucjusza Termusa w oblężeniu miasta Mitylena na wyspie Lesbos, gdzie powierzono mu misję sprowadzenia okrętów od króla Bitynii Nikomedesa IV. Misję tę wykonał, jednak zabawił na dworze na tyle długo, że powstała plotka o romansie z królemSwetoniusz, s. 26.. Epizod w Bitynii dawał pretekst do satyrycznych komentarzy przeciwnikom Cezara, lecz nie wpłynął znacząco na jego karierę polityczną. Po zakończeniu misji Cezar powrócił do Bitynii pod pretekstem prowadzenia spraw sądowych „jakiegoś wyzwoleńca”.