Вскоре после того Лукулл в качестве проквестора сопровождал Суллу в первой Митридатской войне. Сулла Любил благонравного, образованного юношу и питал большое доверие к его способностям и усердию. Когда осада Афин стала для него затруднительной по причине недостатка в кораблях, то он возложил на своего квестора поручение собрать для него флот, задачу трудную и опасную, так как море находилось во власти понтийского флота и кораблей пиратов, состоявших в союзе с Митридатом. Он отправился с шестью кораблями на остров Крит, а оттуда, с полученным там подкреплением, в Кирену, где учреждением свободного управления восстановил на короткое время порядок в расшатавшемся государстве. По дороге в Египет пираты лишили его большей части кораблей. Египетский царь принял его с почетом и дружелюбно, но не дал кораблей, так как и сам состоял в союзе с Митридатом. Под прикрытием царских кораблей он отправился в Кипр, а оттуда в Родос. В Родосе, Косе и Книдосе его эскадра получила некоторое подкрепление, так что ему удалось изгнать царское войско из Хиоса и взять в плен колофонского тирана Эпигона, которому покровительствовал Митридат. Однако он не пожелал прийти на помощь Фимбрию, окружившему Митридата с суши в Питане, гавани Мизии, и просившему его закрыть вход в нее с моря, чтобы царь не мог уйти; как истый аристократ, Лукулл не хотел иметь никакого дела с марианцем и предпочел упустить удобный случай положить скорый конец войне. Нанеся после того поражение царскому флоту у Лектума и Тенедоса, он у фракийского Херсонеса соединился с Суллой и перевез его войско в Азию.

Когда Сулла заключил с Митридатом мир при Дардане (84) и поспешил обратно в Италию, то он оставил Лукулла в Азии с поручением собрать наложенную на тамошние города контрибуцию в 20 тыс. талантов. Лукулл показал себя в этом деле человеком справедливым и бескорыстным и действовал по отношению к истощенным Митридатом жителям с большим снисхождением и мягкостью. Из собранного серебра он, по желанию Суллы, отчеканил в Пелопоннесе монету, которая долго оставалась в обращении под именем Лукулловой. Пробороздив в восточных морях со своей эскадрой еще некоторое время, он возвратился в Рим (80). Счастливый случай удерживал его вдали от Италии во время Сулловых проскрипций и избавил его от позора быть участником, как сподвижника Суллы, ограбления и умерщвления сограждан. Сулла до смерти своей высоко ценил Лукулла; он посвятил ему свои записки, поручив ему в то же время обработать и сгладить их, и, обойдя Помпея, возложил на него опеку над своим сыном Фаустом, что послужило, как полагают, первым поводом к раздору и несогласию между обоими честолюбивыми молодыми людьми.

После того как Лукулл в 79 г, вместе с братом своим Марком занимал должность курульного эдила и в этой должности услаждал народ дорогими и блистательными зрелищами боя слонов и быков, он в 77 г. был избран претором и в следующем году приобрел уважение за справедливое и кроткое управление провинцией Африкой. В 74 г. он был избран консулом вместе с М. Аврелием Коттой. В этом году вспыхнула третья Митридатская война. Бездетный вифинский царь Никомед III завещал перед смертью свое царство римлянам, и они не замедлили занять эту страну. Так как они вследствие этого стали непосредственными соседями Понтийского царства и Митридат увидел, что его господству грозит опасность, то он объявил войну и напал на владения римлян в Азии с войском в 100 тыс. пеших, 16 тыс. всадников, 100 боевых колесниц и хорошо вооруженным флотом в 400 кораблей. Митридат тем более надеялся на счастливый исход дела, потому что Серторий, с которым он заключил союз, немало тревожил римлян в Испании. Но как раз в этом году наступил в Серторианской войне поворот, римляне получили возможность направить все свои силы на Азиатскую войну. Ведение этой войны было возложено на обоих консулов того года; Котта был назначен начальником флота; Лукулл же, как наместник Киликии и Азии, стал во главе сухопутного войска.