He started his military career in 134 BC, as a member of the staff of Scipio Africanus Minor during the Numantine War. Later on, Rufus was a legate of Quintus Caecilius Metellus Numidicus in the campaign against Jugurtha of Numidia of 109 BC, along with Gaius Marius. He distinguished himself in the battle of the Muthul, where he faced a charge by the foe Bomilcar and managed to capture or maim most of the Numidian war elephants. In 105 BC he was elected to the consulship as a junior partner of Gnaeus Mallius Maximus. His main achievements concerned the discipline of the army and the introduction of an improved system of drill. Subsequently, he served as legate to Quintus Mucius Scaevola, governor of Asia.
By assisting his superior in his efforts to protect the provincials from the extortions of the publicani, or farmers of taxes, Rufus incurred the hatred of the equestrian order, to which the publicani belonged. In 92 BC he was charged with the very offence of extortion over those whom he had done his utmost to prevent. The charge was widely known to be false, but as the juries at that time were chosen from the equestrian order, his condemnation was only to be expected, as the order bore a grudge against him. Rufus was defended by his nephew Gaius Aurelius Cotta and accepted the verdict with the resignation befitting a Stoic and pupil of Panaetius.
He retired to Mytilene, and afterwards to Smyrna, where he spent the rest of his life (possibly as an act of defiance against his prosecutors: he was welcomed with honour into the very city he was prosecuted for allegedly looting), and where Cicero visited him as late as the year 78 BC. Although invited by Lucius Cornelius Sulla to return to Rome, Rufus refused to do so. It was during his stay at Smyrna that he wrote his autobiography and a history of Rome in Greek, part of which is known to have been devoted to the Numantine War. He possessed a thorough knowledge of law, and wrote treatises on that subject, some fragments of which are quoted in the Digests. He was also well acquainted with Greek literature.