Nommé questeur de Marius, alors consul pour la première fois, il le suivit en Afrique dans la guerre contre Jugurtha. A peine arrivé à l’armée, il s’y fit de la réputation par son courage ; et, ayant su profiter d’une circonstance heureuse, il gagna l’amitié de Bocchus, roi des Numides. II avait recueilli des ambassadeurs de ce prince, qui s’étaient échappés des mains de brigands numides ; et, après les avoir traités avec la plus grande générosité, il les avait renvoyés, comblés de présents, sous une bonne escorte. Bocchus craignait et haïssait de longue main Jugurtha son gendre, qui, vaincu par les Romains, s’était réfugié chez lui. Résolu de le trahir, il appela auprès de lui Sylla, aimant mieux que ce fût lui qui le prît et le livrât aux Romains que de le leur livrer lui-même. Sylla, après avoir communiqué l’affaire à Marius, prit un petit nombre de soldats, avec lesquels il alla s’exposer au plus grand péril, en se confiant à un Barbare qui manquait de foi à ses plus proches ; et, pour retirer Jugurtha de ses mains, il alla s’y mettre lui-même. Quand Bocchus les vit l’un et l’autre en sa puissance, et qu’il se fut mis dans la nécessité de trahir l’un des deux, il flotta longtemps entre des résolutions opposées ; enfin, il se décida pour la première trahison qu’il avait projetée, et remit son gendre entre les mains de Sylla. A la vérité, ce fut Marius qui mena ce prince en triomphe ; mais, par l’envie qu’on portait au consul, on attribuait à Sylla la gloire d’avoir fait Jugurtha prisonnier. Marius en conçut un violent dépit, que la conduite de Sylla ne fit qu’augmenter encore. Naturellement vain et longtemps ignoré dans Rome, il commençait à acquérir de la considération. Séduit par cette première amorce de gloire, il en vint à cet excès de vanité de faire graver cet événement sur un anneau qu’il porta toujours depuis, et qui lui servait de cachet. On y voyait Bocchus qui livrait Jugurtha, et Sylla qui le recevait de ses mains.

Quelque déplaisir qu’en eût Marius, il fit réflexion que Sylla n’était pas encore un personnage assez important pour exciter sa jalousie, et il continua de l’employer à l’armée. Dans son second consulat, il le fit son lieutenant ; et dans le, troisième, il lui donna la charge de tribun des soldats. Dans ces divers emplois il lui dut de grands succès. Pendant sa lieutenance, Sylla fit prisonnier Copillus, général des Gaulois Tectosages ; et, dans son tribunal, il attira les Marses, nation nombreuse et guerrière, dans l’alliance des Romains. Mais, s’étant aperçu que Marius était toujours son ennemi secret, qu’il ne lui donnait qu’à regret des occasions de se signaler, et qu’il nuisait même à son avancement, il s’attacha à Catulus, collègue de Marius dans le consulat, homme honnête, mais un peu lent pour les opérations militaires. Bientôt Sylla, à qui Catulus confia les entreprises les plus importantes, acquit autant de puissance que de réputation. Il soumit la plupart des Barbares qui habitaient les Alpes ; et, l’armée romaine ayant manqué de vivres, Sylla, chargé par Catulus du soin d’en procurer, en fit venir une si grande abondance, que les soldats de Catulus en eurent au-delà de leurs besoins et en fournirent à l’autre armée, ce qui, au rapport de Sylla lui-même, dans ses mémoires, mortifia beaucoup Marius. Ainsi leur haine, qui avait pris sa source dans des causes si faibles et si puériles, nourrie ensuite par les séditions, et cimentée du sang des guerres civiles, aboutit enfin à la tyrannie et au renversement total de la république. Cet exemple fait connaître la sagesse d’Euripide, et la profonde connaissance qu’il avait des maux politiques, lorsqu’il recommandait surtout d’éviter l’ambition, comme la peste la plus pernicieuse et la plus funeste à ceux qui s’y livrent.

Sylla, ne doutant point que la gloire qu’il avait acquise par les armes ne lui suffît pour prétendre aux dignités civiles, passa des emplois de l’armée aux brigues populaires, et se mit sur les rangs pour la préture de Rome ; mais il fut refusé. Il en attribue lui-même la cause à la populace, et dit que cette dernière classe de citoyens, qui savait ses liaisons avec Bocchus, et qui s’attendait qu’en le nommant édile avant de le faire préteur, il donnerait des spectacles magnifiques de chasses et de combats de bêtes d’Afrique, nomma d’autres préteurs, dans l’espérance qu’elle le forcerait à demander l’édilité. Mais il paraît avoir dissimulé la véritable cause de ce refus, et les faits mêmes le prouvent : car, l’année suivante, ayant gagné le peuple, soit par son assiduité à lui faire la cour, soit par ses largesses, il fut nommé préteur. Aussi, pendant qu’il exerçait la préture, ayant dit en colère à César : « J’userai contre vous du droit de ma charge, - Vous avez raison, lui répondit César en riant, de dire votre charge ; elle est bien à vous, puisque vous l’avez achetée. » Après sa préture, il fut envoyé en Cappadoce. Le prétexte apparent de cette expédition était de ramener Ariobarzane dans ses états, mais elle avait pour véritable motif de réprimer les entreprises ambitieuses de Mithridate, qui se mêlait de tout, et travaillait à se faire un empire du double plus étendu que celui qu’il possédait déjà. Sylla n’avait emmené que fort peu de troupes ; mais, ayant employé celles des alliés, qui le servirent avec zèle, il tailla en pièces un grand nombre de Cappadociens, et un corps plus nombreux encore d’Arméniens venus à leur secours, chassa Gordius du trône de Cappadoce et y rétablit Ariobarzane. Pendant qu’il était sur les bords de l’Euphrate, il reçut dans son camp le Parthe Orobase, ambassadeur du roi Arsace. Les deux nations n’avaient encore eu aucun commerce ensemble, et l’on regarda comme un grand effet de son bonheur qu’il fût le premier à qui les Parthes eussent envoyé des ambassadeurs pour rechercher l’alliance et l’amitié des Romains. A la réception de cet ambassadeur, il fit, dit-on, dresser trois sièges, l’un pour Ariobarzane, l’autre pour Orobase, et un troisième au milieu, sur lequel il se plaça pour lui donner audience. Le roi des Parthes fit mourir Orobase, pour avoir laissé avilir ainsi sa dignité. Sylla fut loué par les uns d’avoir traité des Barbares avec cette fierté ; d’autres le taxèrent d’une arrogance insultante et d’une ambition déplacée. On raconte qu’un Chalcidien de la suite d’Orobase, ayant fixé Sylla et considéré avec beaucoup d’attention tous les mouvements de son corps, toutes les expressions de sa pensée, appliqua les règles de son art à ce qu’il avait saisi de son caractère, et dit que cet homme parviendrait nécessairement au plus haut degré de grandeur, et qu’il était même surpris comment il pouvait souffrir dès à présent de n’être pas le premier de l’univers. Quand il fut de retour à Rome, Censorinus l’accusa de péculat, pour avoir, contre les lois, emporté de grandes sommes d’argent d’un royaume ami et allié ; mais il se désista de son accusation, et l’affaire ne fut pas portée en justice.