Between 81 and 79, Caesar served in Asia Minor on the personal staff of Marcus Minucius Thermus, who was praetor in Asia Minor. Caesar was sent on a diplomatic mission to king Nicomedes of Bithynia and seems to have had a love affair with this ruler; during the conquest of the island Lesbos, Caesar gained a prize for bravery (corona civica); later, he was captured by pirates, and payed the usual ransom, 25 talents (500 kg) of silver.
When Sulla died (78), Caesar felt save to return to Italy, where he started a career as a criminal lawyer. This was a normal thing to do, and Caesar stayed far from politics. In 75, he went to Rhodes for further education, and again he was captured by pirates, who asked the usual tariff. Caesar demanded this prize to doubled (after all, he was an aristocrat) and promised to kill his captors. After the ransom was payed, Caesar manned some ships, defeated the bandits and had them crucified. After this incident, he continued his studies.
They were interrupted, however, when Mithridates of Pontus attacked Asia Minor a second time (74). On his own initiative and expenses, Caesar raised a small army and defended some towns, giving the official Roman commander Lucullus time to organize an army and attack Mithridates in Pontus. Being a war hero by now, Caesar returned to Rome in 73. A career as a general and a politician had started.
In 68, he was elected quaestor and served in Andalusia. (A quaestor was an officer who was detached to a provincial governor and whose duties were primarily financial.) Before Caesar's departure, Marius's widow died, and he held a funeral speech in which he praised his aunt and her family. This was a way of claiming Marius' inheritance. That Caesar had developed political ambitions is shown by an incident in Spain: in Gades he saw a statue of Alexander the Great, and remarked that he had as yet performed no memorable act, whereas at his age -33 years old- Alexander had already conquered the whole world.
After his return from Spain, Caesar was elected aedile (in 65) and responsible for "bread and circuses". He organized great games, making sure that the Roman mob would remember his name: in this way, as a true popularis, he would control their votes in the People's Assembly. This same year, he was accused of complicity in a plot to murder the consuls, but he was not sentenced. The leader of the plot, one Catilina was able to continue his career as a social reformer.
Two years later, Caesar managed to be elected pontifex maximus or high priest. He had paid large bribes. In this capacity, he proposed a moderate line against the followers of Catilina, who had made a second attempt to seize power. This second conspiracy was discovered by the consul Cicero, who had Catilina's followers executed at the instigation of Cato the Younger, a representant of the traditionalist wing of the optimates. Caesar's opposition to the death penalty again represents his `popular' policies, and probably he knew more about the plot than he liked to show.
Nevertheless, he was elected praetor, and the optimates became nervous for the first time, because Caesar was extremely popular with the masses. This time, they managed to rise accusations against Caesar, who they said was involved in a desecration of certain secret ceremonies. These ceremonies of the so-called Good Goddess were celebrated exclusively by women in the house of the pontifex maximus, but a man had been able to be present. The optimates argued that the high priest must have been involved too, and Caesar's only way to prevent larger troubles, was to divorce his wife.
Caesar was bankrupt by now. He had paid for the games of 65, the lobby for the pontificate in 63 and had paid much money to get out of the Good Goddess affair. Marcus Licinius Crassus, the richest man in Rome, paid Caesar's debts (830 talents, 17,500 kg silver) and Caesar had himself elected governor of Andalusia.
Until now, Caesar's behaviour had been more or less normal for a Roman senator with strong ambitions. From now on, however, Caesar's acts were often criminal, and Caesar's problem seems to have been that he had to possess an office or an army command, just to make sure that he had an immunity against prosecution.
Caesar's Spanish War gives a foretaste of the Gallic Wars. There was some unrest in the province, and under the pretext of restoring order, Caesar captured several towns, looted them, and made a lightning attack along the west-coast (through modern Portugal) and plundered the silver mines of Gallicia. When a town was under siege, and surrendered, it was nonetheless ravaged. As a rich man, Caesar returned, being able to sponsor a lobby for both the consulate and the right to enter the city with his army in an official procession (triumphus). Of these two, the triumph would give him most popularity, but the consulship was a necessity: he was likely to be prosecuted as a war criminal and the only way to prevent a law suit was an office. Having both was impossible, as Cato the Younger had announced the day of the consular elections, and no account of Caesar's candidacy could be taken unless he was a private citizen. Caesar was forced to forego his triumph in order to avoid losing the necessary consulship.