Однако это было очень нелёгкой задачей, поскольку именно в Малой Армении Евпатор подготовил мощнейшую военную базу, опираясь на которую он мог без особых усилий вести войну. Получать подкрепления, оружие, деньги и продовольствие. «
Легаты советовали Лукуллу временно приостановить боевые действия, указывая на трудности предприятия, но Луций Лициний с ними не согласился и через Вифинию и Галатию начал вторжение в Понт. Главной проблемой для Лукулла на первом этапе похода стал острый недостаток продовольствия, поскольку местность была разорена боевыми действиями. Но проконсул сумел решить эту проблему. По приказу Луция Лициния согнали 30 000 галатов, нагрузили каждому на плечи по медимну[37] зерна и отправили следом за легионами. Так римляне и шли до тех пор, пока не оказались в не затронутых войной местах. Здесь ситуация изменилась радикально. Вокруг царило такое изобилие, что легионеры зажрались в буквальном смысле слова. Как свидетельствует Плутарх, часть добычи они просто бросали, либо уничтожали.
Однако добраться до вражеской армии Лукуллу было не так-то просто, поскольку по пути пришлось заниматься осадой больших и хорошо укреплённых городов – Амиса, Евпатории и Фемискиры. Амис и Евпатория находились на близком расстоянии друг от друга, причём последняя считалась царской резиденцией. Жители Амиса оказали героическое сопротивление захватчикам. Они отражали вражеские приступы, сами делали вылазки, а многие из защитников выходили за стены города и вызывали сыновей волчицы на единоборство.
Ещё большие трудности испытали римляне при осаде Фемискиры, города, расположенного на реке Фермодонт, где согласно мифам проживали легендарные амазонки. Бои за Фемискиру с самого начала приняли такой ожесточённый характер, что римляне сразу же пустили в дело весь свой богатый осадный арсенал. Насыпав огромные насыпи и соорудив множество осадных башен, они попробовали прорваться в город через стены, но потерпели неудачу. Тогда Лукулл пошёл другим путём. По его приказу под укрепления повели подземные ходы очень больших размеров, надеясь с их помощью обрушить стены и проникнуть в город. Но и эта затея не увенчалась успехом. В подземных коридорах, при тусклом свете чадящих факелов, гоплиты Фемискиры сходились врукопашную с легионерами, всякий раз отбрасывая противника назад. Осажденные порывали сверху отверстия в римские ходы и выпускали туда медведей и других диких животных. Чтобы сделать жизнь римлян, работающих под землёй, совсем невыносимой, горожане запускали туда рои диких пчёл.
Яростная битва не затихала ни на один день, а успехи у Лукулла были более чем сомнительны. Мало того, Митридат, который всю зиму собирал армию у Кабиры, постоянно поддерживал гарнизон Фемискиры, посылая в город подкрепления, а также большое количество продовольствия и оружия. Царь рассчитывал, что пока римская армия будет связана осадой крупных городов, у него будет столь необходимое время, чтобы собрать и обучить новое войско. И судя по всему, эти расчёты стали оправдываться. Под знамёна Митридата собралось 40 000 пехоты и 4000 конницы. Но в бой с Лукуллом царь пока вступать не спешил, справедливо полагая, что чем дольше он останется на месте, тем больше увеличатся его силы. Зато силы римлян будут уменьшаться. Это понимал и римский командующий, однако надеялся, что Митридату надоест сидеть зимой в горах и он явится на выручку осаждённым городам.
Так оно и тянулось до весны, а там терпение у Лукулла лопнуло. Осознав, что Митридат не собирается покидать свои позиции, проконсул решил сам двинуться вперёд и дать бой Евпатору. Весной 71 г. до н. э. римский полководец повёл легионы против Митридата. В тылу, под командованием Мурены остались войска для осады Амиса, а также блокады Евпатории и Фемискиры. Война вступила в решающую фазу.
