Marius' early military career – as well as that of Publius Rutilius Rufus – was in Spain under Publius Cornelius Scipio Aemilianus Africanus Numantinus (or Africanus Minor), the final victor of Carthage who later fought the Celtiberians and defeated them definitively at Numantia in 133 BCE. Appian discusses that war.
Marius then went on to a political career and got as far as praetor, after which it stalled. It was revived after he served, together with Rutilius Rufus, as senior legate under Quintus Caecilius Metellus (later named “Numidicus”) in the war against Jugurtha in 109 BCE. In 108, Marius became consul himself and continued the war against Jugurtha. It was then that he had to go the capitecensi for recruiting, the Roman headcount, in order to get an army together – due to the exhaustion of soldier material, especially after two devastating defeats by the Germans. (The worst defeat, at Aurasio, was still to come.) At the same time, he began the reform and restructure the army itself, while Rutilius Rufus wrote an army drill manual.
In a recent blog, Dorothy King, who is writing a book on Marius, pointed out his military reforms and provided a pdf link to C.J. Lyes: How Revolutionary were the Military Reforms of Gaius Marius? The article discusses the army history leading up to recruiting the capitecensi, an overview of the reforms, and the possible motives of Marius. Lyes also refers to Sallust as a hostile source:
LXXXVI. After having spoken to this effect, Marius, when he found that the minds of the populace were excited, immediately freighted vessels with provisions, pay, arms, and other necessaries, and ordered Aulus Manlius, his lieutenant-general, to set sail with them. He himself, in the mean time, proceeded to enlist soldiers, not after the ancient method, or from the classes [254], but taking all that were willing to join him, and the greater part from the lowest ranks. Some said that this was done from a scarcity of better men, and others from the consul's desire to pay court [255] to the poorer class, because it was by that order of men that he had been honored and promoted; and, indeed, to a man grasping at power, the most needy are the most serviceable, persons to whom their property (as they have none) is not an object of care, and to whom every thing lucrative appears honorable. Setting out, accordingly, for Africa, with a somewhat larger force than had been decreed, he arrived in a few days at Utica. The command of the army was resigned to him by Publius Rutilius, Metullus's lieutenant-general; for Metullus himself avoided the sight of Marius, that he might not see what he could not even endure to hear mentioned. (The Jugurthine War at Ancient/Classical History at About.com)
