Kr. e. 109-ben, 10 évvel fivérét követően elnyerte a consuli magistraturát Marcus Junius Silanusszal közösen. Tartománya Numidia lett, ahol a lázadó Jugurtha király elleni háború irányítása lett a feladata. A numidiai uralkodó korábban megalázó helyzetbe hozta a római hadsereget a hadvezérek korruptságának és hozzá nem értésének köszönhetően, azonban Metellus hamarosan kiköszörülte a csorbát: a Muthul folyónál fényes győzelmet aratott az afrikai csapatok felett. A következő évben proconsulként a tartományban maradt, azonban mivel leginkáb városok ostromával volt elfoglalva, a sikerek ellenére nem ért el döntő győzelmet a háborúban.

Metellus hadseregében legatusként szolgált Caius Marius is, akinek eddigi karrierjét patrónusként elősegíteni igyekezett. Azonban az alacsony származású Marius többször is kérte, hogy hazatérhessen a hadszíntérről, hogy indulhasson a consulválasztáson - az arisztokrata Metellus ebbe nem volt hajlandó beleegyezni.
Hivatkozott arra, hogy Mariusra nagy szükség van a hadszíntéren, és hogy biztos bukás vár rá; egy alkalommal meg is sértette, amikor azt találta mondani, hogy a tiszt ráér a consulságra pályázni a fiával együtt. Márpedig Metellus fia, Quintus ekkor még csak húszéves volt, azaz körülbelül húsz évet kellett volna várnia arra, hogy megválaszthassák.

A sértett Marius szorgalmasan munkálkodott azon, hogy a hadvezér pozícióját megrendítse. Mind a táborban, mind Rómában módszeresen elhíresztelte, hogy Metellus szándékosan húzza-halasztja a végső ütközetet, hogy tovább maradhasson főparancsnok. Ezzel el is érte célját: consullá választották, tartománya pedig Numidia lett, így a hadjárat befejezésének dicsőségétől is megfosztotta a proconsult. Ezzel olyannyira kivívta Metellus ellenszenvét, hogy az látni sem kívánta őt: legatusára, Publius Rutiliusra hagyta a hadseregét, és idő előtt elindult haza, hogy ne neki kelljen átadni a főparancsnokságot. Mindezek ellenére Rómában üdvrivalgással fogadták, és Kr. e. 107-ben triumphust tarthatott. Ekkor nyerte el a megtisztelő Numidicus agnoment (ragadványnév latinul).