As Quaestor under Marius in the Jugurthine War, he had proved a most active and useful officer." In these African campaigns he showed that he knew how to win the hearts and confidence of his soldiers; and through his whole subsequent career, the secret of his brilliant successes seems to have been the enthusiastic devotion of his troops, whom he always held well under control, even when they were allowed to indulge in plunder and license.

It was to Sulla's combined adroitness and courage that Marius owed the final capture of Jugurtha.

He served again under Marius in the campaigns against the Cimbri and Teutones, and gave efficient help towards the victory.

But the Consul became jealous of his rising power, and all friendly feeling between the two ceased.
After this campaign Sulla lived at Rome for some years, taking no part in politics, and during this time his name and that of his rival are almost unheard.

He appeared before the public again in 93, when he was elected Praetor, and increased his popularity by an exhibition of a hundred lions in the arena, matched against Numidian archers.