In 107 v.C. word Sulla tot ''quaestor'' verkies. Hy kom in diens van konsul Gaius Marius wat na die huidige Algerye[[Algerië]] gestuur word om Jugurtha van Numidië te onderwerp. Jugurtha kry steun van sy skoonpa koning Bocchus van Mauretanië (die huidige [[Marokko]]).<ref name="Telford" />
Sulla skep 'n leërtjie ruiters in ItaliëItalia en vertrek na Africa om Marius te help in sy oorlog teen Jugurtha. Met sy toneelervaring vermag hy om homself baie populêr te maak by sy mans, wat hy altyd met groot respek behandel. Sulla speel 'n belangrike rol in die beëindiging van hierdie oorlog. Marius gee hom die amp van ''quaestor propraetore'' wat beteken dat hy die bevel het oor die Romeinse kamp in Utica toe Marius self Rome toe gaan. Sulla knoop betrekkings aan met Bocchus wat Jugurtha aan die Romeine uitlewer en die Jugurthynse oorlog word beëindig. Marius kan so in Rome op 1 Januarie 104 v.C. 'n triomftog hou. Sulla kry min beloning vir sy rol in Marius se sukses, behalwe moontlik dat koning Bocchus wat nou 'n vriend en bondgenoot van Rome is, vir hom 'n vergulde standbeeld op die Forum Romanum laat plaas.<ref name="AK" />
