After Crassus' victory over Spartacus and Pompey's triumphant return from Spain, both men were elected Consul for 70 BC. While both men had little affinity for the other, they made a public reconciliation to ease fears of further civil wars. In office, they often opposed each other on legislation efforts, but the relationship was at least maintained civilly. Both had various agendas for their Consular terms; Pompey strived for the settlement of his veterans in particular, but neither accomplished much of great importance. Though various unpopular laws of Sulla were reversed, including the restoration of the Tribunal veto, true political power for them wouldn't come until a decade later.
For the time being, however, events were unfolding in the east that would soon require the attention of Pompey. In the late 70's BC, war with Mithridates erupted once again, and would last several years. The region of Cyrenaica, under client status, required organization as a province, and the activities of Cilician pirates throughout the Mediterranean was a growing problem that needed attention.
In 96 BC the king of Cyrene, Apion, willed his kingdom to Rome. Lacking enough proper magistrates,
however, the Senate allowed a self rule among the various city states including Cyrene rather than establishing an official province. By 74 BC though, the various Greek cities of the area were under heavy pressure from Libyan natives and the situation was dire. Despite Sulla's creation of additional magistrates, there was still a lack of potential officials to take control and a low ranking Quaestor had to be sent. Despite this, the territory was secured and administered into an official province with little difficulty.
Cilician pirates, on the other hand, had been a long and continuing nuisance for Rome. In 102 BC, Marcus Antonius (grandfather of Marc Antony) was sent to deal with the pirates off the coast of Asia Minor. 25 years later, the efforts of Antonius had little effect. Servilius Vatia operated against the pirate between 78 and 75 BC, but despite his victories, and triumphant reward of the title Isauricus, little was really done to end the pirate threat. By 74 BC, the son of the first Antonius (father of Marc Antony) was granted the appointment of Imperium Infinitum throughout the Mediterranean. With this new command, he was granted authority of operation throughout the entire sea, regardless of provincial authorities. He did much to reduce the pirate threat, but by the time of Pompey, they were still raiding the Italian coast. Quintus Caecilius Metellus was sent to Crete to put an end to Roman resistance there, and managed to do so with the authority of Pompey. By 66 BC, Crete was delivered as a Roman province and Metellus was granted the title of Creticus. Pompey would then go a long way to eradicate piracy during his eastern campaigns.
In 74 BC, King Nicomedes of Bithynia died and willed his kingdom to Rome. Mithridates, however, desired the territory for his own expansionist ideas, and Roman acceptance of the will would clearly lead to war. In 73 BC, M. Aurelius Cotta was appointed to establish Bithynia as a province and L. Licinius Lucullus was given Cilicia as an additional counter measure to Mithridates. Soon after Cotta's arrival, and the official designation of Roman authority, Mithridates invaded Bithynia. With Cotta under siege, Lucullus marched north to help, and it wasn't long before Mithridates was forced to withdraw. Cotta then besieged towns loyal to Mithridates and eventually returned to Rome after a successful outcome in 71 BC.
Lucullus had success as well, destroying a Mithridatic army near Cabira. Mithridates retreated to Armenia, where his son-in-law Tigranes ruled. After forcing Roman authority on remaining resistance to his rear including Pontus, Lucullus was ready to pursue Mithridates by 70 BC. At first things went well for the Romans, but over the next three years, the tide of the war went back and forth. Lucullus was unable to complete his conquests in Armenia and Mithridates took back Pontus in the interim. By 67 BC, Lucullus army was in a state of mutiny and his chances for glory had come to an end with little to show for it. A law passed by the Tribune A. Gabinius effectively stripped Lucullus of his command and gave it to one of the current consuls, M. Acilius Glabrio.