Похвалы молодому квестору раздражали старого популиста, и хотя Марий по-прежнему пользовался услугами Суллы, повышая его в ранге после каждого нового похода, вскоре зависть старика вынудила Суллу искать себе других покровителей. Приняв под свое начало войска консула Катула, Сулла покорил варварские альпийские племена. Когда ранние зимние ветры приперли легионы, не имевшие достаточных припасов, к подножию гор, Сулла мастерски изменил маршрут и доставил свежий провиант не только своему войску, но и войску Мария, который просто побагровел от негодования. Такие-то уколы мелочной ревности и положили начало длительному, изматывающему соперничеству Суллы и Мария, которое впоследствии причинило Риму столько бед и несчастий.
Сулла отправился на Восток, и Фортуна привела его к новым победам в Каппадокии. С дипломатической миссией он дерзнул добраться до самого Евфрата и стал первым должностным лицом, вступившим в дружеские переговоры с Парфянским царством, которое владеет всем остальным миром. Его обаяние (или слепая надменность) ослепило парфянского посла, согласившегося сесть ниже Суллы, подобно просителю перед лицом римского владыки. Впоследствии парфянский царь казнил посла: потеряв лицо, он потерял и голову — эту шутку не уставал повторять Сулла.
Ни один могущественный правитель не может обойтись без предзнаменований своего будущего величия, сопутствующих его легенде; при рождении Александра с неба сыплются звезды, Геркулес душит в колыбели змей, при появлении на свет Ромула и Рема над землей сражаются орлы. Именно встреча с парфянами положила на жизненный путь Суллы печать легендарности. Правда то или выдумка — никто, кроме Суллы, теперь не может сказать это наверняка, — но предание гласит, что входивший в парфянскую свиту ученый халдей внимательно изучил лицо Суллы и постиг его характер, используя принципы науки, неизвестной Западу. Вероятно, он выискивал слабости, о которых смог бы донести своим парфянским господам, но вместо этого мудрец в изумлении опустил руки. Сулла, никогда не отличавшийся ложной скромностью, дословно передает реакцию старого халдея в своих «Записках»: «Может ли человек быть столь великим и в то же время не величайшим из всех живущих? Я потрясен — но не его величием, а тем, что даже теперь он воздерживается занять подобающее ему место среди граждан, коих он во всем превосходит».
Когда Сулла вернулся в Рим, Марий не был рад его видеть.
Яблоко раздора подкинул царь дружественной Нумидии, прислав в Рим статую, увековечившую память об окончании африканской войны и падении Югурты. Распростертые крылья Победы осеняли фигуру царя, который передавал скованного Югурту лучшему своему другу — Сулле. Марий изображен не был. Разъяренный от ревности старик едва не лишился рассудка при мысли о том, что Сулла украл его славу, и угрожал уничтожить статую собственными руками, если сенат не постановит убрать ее с Капитолия. Риторическая буря с обеих сторон не унималась до тех пор, пока разрыв не стал необратимым. Вспышка насилия казалась неминуемой, но в этот момент грянула союзническая война между Римом и его италийскими подданными, и все личные распри были перенесены на будущее.