An de Rome 658 (-96): Sylla obtient la province de Cilicie à gouverner. A cette époque, il existe en effet six provinciae praetoriae attribuées par tirage au sort aux préteurs élus. Cette province romaine est nouvelle; elle a peine six ans d'existence. Et le poste de gouverneur de Cilicie n'en est pas un à proprement parlé. En effet, le terme provincia Cilicia désigne avant tout un commandement maritime. Il s'agit de mener des expéditions contre les pirates qui empêchent la bonne marche du commerce entre Rome et ses provinces d'Orient. Sylla part donc avec une toute petite troupe. Cependant, Rome avait désigné Sylla pour une autre mission: ''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 allait se mêlant de tout, et agrandissant au double l'empire et la puissance qu'il possédait déjà'', explique Plutarque. Ce qui mortifia une nouvelle fois Marius qui espérait bien se voir confier cette mission. Mais avec Sylla, le Sénat tenait ''son'' général et pouvait désormais se passer des services de Gaius Marius.
Mithridate a conquis le royaume de Cappadoce vers 654 (-100). Le roi du Pont tua de sa propre main le roi Ariarathe VII de Cappadoce et installa sur le trône son fils de huit ans, Ariarathe IX Eusèbe Philopator. Il nomme son homme de main Gordios pour exercer la régence. C'est cet événement qui décida Marius à déclencher une guerre contre Mithridate. Ne pouvant obtenir le commandement espéré, Marius se rendit en Cappadoce afin de rencontrer Mithridate, et susciter quelques troubles dans la région. Se fut un nouvel échec pour Marius, qui du se contenter de menace verbales contre Mithridate. De son côté, la Bithynie se sentait menacée. Elle envoya une ambassade à Rome pour demander le royaume de Cappadoce. Apprenant cela, Mithridate envoya Gordios à Rome pour légitimer son fils sur le trône. Le Sénat refusa de reconnaître Ariarathe IX et demanda à ce que la Cappadoce devienne une République (fin 656/-98). Mais les Cappadociens répondirent qu'ils préféraient être gouvernés par un roi et élurent à ce poste un grand seigneur perse, Ariobarzane (milieu 657/-97). Ariarathe IX et Gordios refusent de reconnaître Ariobarzane et le chasse de Cappadoce. Bien que légalement élu, Ariobarzane quitte le pays et part se réfugier à Rome (fin 657/-97). Sylla, en tant que gouverneur de Cilicie, fut donc chargé d'aller remettre Ariobarzane sur son trône.
Ariobarzane
Sylla débarqua donc en Cilicie au printemps avec Ariobarzane. Cependant, il ne disposait que d'une petite troupe et devait recruter des auxiliaires auprès des alliés avant d'entamer une quelconque campagne militaire. Il recruta donc largement chez les Ciliciens. A force de persuasion et de ténacité, ses troupes atteindront l'effectif assez remarquable de quatre légions.
Les Monts Taurus
A l'été, Sylla franchit les monts Taurus avec ses troupes et marcha droit sur la capitale de Cappadoce Eusebeia Mazaca. En chemin, il réussit à défaire l'armée pontico-cappadocienne au prix de sanglants affrontements.
An de Rome 659 (-95): Sylla et Ariobarzane n'allèrent pas tout de suite à Eusebeia Mazaca. Gordios avait en effet appelé les Arméniens, voisins de la Cappadoce, à son secours. L'Arménie était en pleine effervescence. Son roi Tigrane vient de mourir. Son arrière-petit-fils, Tigrane, alors prisonnier des Parthes, obtient le droit de monter sur le trône de l'Arménie en échange d'un vaste territoire. Sylla alla donc affronter l'armée arménienne, plus ce qui restait de l'armée cappadocienne et, grâce aux tactiques de guerres romaines, il parvint à les mettre en fuite. Désireux d'annihiler toutes velléités, Sylla poursuivit ce qui restait de l'armée arménienne jusqu'au bord de l'Euphrate.
Les rives de l'Euphrate
Alors qu'il parcourait les bords de l'Euphrate pour éradiquer les dernières poches de résistance, Sylla eut la surprise de voir venir à lui une délégation parthe. Le roi Tigrane d'Arménie était un de leurs vassaux, et les Parthes ne voyaient pas d'un bon œil les Romains s'immiscer dans leurs affaires. Lucius Cornelius accepte de recevoir la délégation et prépara une petite mise en scène. A cette époque, l'Empire Parthe est aussi puissant que l'Empire Romain. Le territoire des Parthes s'étend en effet de l'Euphrate jusqu'à l'Inde. Sylla doit donc faire forte impression sur la délégation parthe car il est le représentant de Rome. Lucius Sylla fait alors préparer trois sièges: celui du centre pour lui, les deux autres pour Ariobarzane et l'ambassadeur parthe Orobaze, représentant du roi Arsacès. N'avoir pas placé l'ambassadeur parthe au centre fut ressenti comme une insulte par les Parthes, et cela vaudra à Orobaze d'être exécuté par le roi Arsacès à son retour. Mais c'était la première fois que les Parthes et les Romains se rencontraient officiellement, et Sylla a profité d'être en position de force pour affirmer le pouvoir de Rome.
Un Parthe
De fait, Sylla, revêtu de tous les insignes et de la dignité et s'exprimant en grec, fit très forte impression sur les Parthes. Selon Plutarque, d'après une version probablement embellie par Sylla, un devin chaldéen de la suite d'Orobaze, qui observait attentivement le proconsul romain fit ce commentaire: il ''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''. Cependant, la vraie version de la scène était aussi impressionnante: ''Il avait été le premier des Romains à recevoir les ambassadeurs des Parthes; il avait consulté quelques uns d'entre eux qui étaient mages et ils répondirent que certaines marques imprimées sur son corps indiquaient qu'il égalerait les dieux avant et après sa mort'' écrit Velleius Paterculus. Sur le plan diplomatique, la rencontre se solda par un traité d'amitié entre les deux peuples, reconnaissant les frontières d'influence entre les Parthes et les Romains et signant un pacte respectif de non-agression. Ainsi, Sylla étendit officiellement l'influence romaine jusqu'à l'ouest de l'Euphrate.
Muni du traité Parthe, Sylla et Ariobarzane allèrent rencontrer Tigrane. Battu, le nouveau roi d'Arménie ne pouvait que concéder la paix à Rome etGordios, qui avait sollicité l'aide arménienne fut donc contraint de quitter la Cappadoce avec Ariarathe. Sylla avait donc réussit sa mission: Ariobarzane était installé sur son trône de Cappadoce, Gordios et son armée vaincue rentrèrent au royaume du Pont, et Tigrane n'avait plus qu'à s'incliner devant le traité parthe.
Tigrane
Sylla et Ariobarzane pouvait donc aller à Eusebeia Mazaca. Ariobarzane devient officiellement roi de la Cappadoce et prend le surnom grec de Philoromeos, soit ''ami des Romains''. Notons que la petite armée romaine tira un bon profit de sa campagne militaire car, le propréteur avait autorisé le pillage des bourgades restées fidèles à Gordios et à Mithridate. Sylla en profita pour aller à Comana et s'initier au culte à mystère de la déesse Mâ. Puis il regagna la Cilicie afin d'organiser au mieux la garnison permanente de la province et veiller à ce que les pirates ne perturbent plus le commerce maritime.