With his new found good fortune, coming in the form of marriage to Julia Caesar, and his apparent reconciliation with the Metelli family, Marius was in a position to make political strides. At this time, the War with Jugurtha had been carrying on for nearly 4 years in Numidia. With no settlement in sight, and charges of corruption and bribery running rampant against the Roman generals in charge of the operation, Quintus Caecilius Metellus was elected Consul in 109 BC. Charged with carrying out the Roman war effort against Jugurtha, Metellus knew Marius was a quality soldier, and appointed him to serve as his chief Legate.
Metellus' first two years in Africa were much the same result as his predecessors. Aside from some minor victories by Marius, the Romans did little to really alter the situation. Marius, sensing the political and popular frustration in Rome, had the perfect opportunity to run for Consul on the basis of being able to finish the war. His time spent as Metellus' subordinate was put to good use by ensuring good terms and popularity among the legionaries. He put the word out to those friends he had in Rome that he alone could win the war, and that the people must elect him. Campaigning essentially through others, and in abstentia, Marius went to Metellus to request dismissal from his service so that he could return to Rome for proper campaigning. Marius was abruptly refused and was forced to continue using his client base to run his campaign. Presenting himself as the blunt, honest general with more capability, and without personal motivation, he was presented as the popular alternative to the ineptness and corruption of the aristocratic elite. Eventually, with the stalemate in Numidia continuing, the strategy worked, and in 107 BC Gaius Marius was elected Consul for the first time.
Metellus was recalled even though the senate wanted to continue his service in Numidia as Proconsul. Through more political wrangling (some say illegal), Marius managed to be appointed as commander in Africa. Due to a military crisis from Germanic victories in Gaul, Marius was forced to take unprecendented measures and recruit his armies from the Roman landless masses. Even so, within two years, Marius completed what he said he would, conquering Numidia and putting an end to the war. Though, there was military success in the field, it was through the service of a young patrician officer, Lucius Cornelius Sulla that the war finally came to a close. Jugurtha himself was betrayed by his ally Bocchus, the King of Mauretania, into the arms of the Romans. Sulla organized the capture, but Marius, having Imperium as Consul, would receive the credit, while Sulla maintained the war only ended through his achievement. The incident was the beginning of a terrible rivalry between the two men that would have monumental repercussions in later years.
For the time being, however, Marius was at the beginning of his hold on Roman political power. Germanic invasions into northern Italy would propel Marius to new heights and his reform of the armies would have an impact on the Roman social structure, previously unmatched. Even the attempted reforms of the Gracchi brothers would pale in comparison to what Marius did.