Новый поход Евпатор организовал в Пафлагонию, поскольку после смерти Митридата V Эвергета она вышла из-под понтийского контроля. Тогда римляне надавили на царицу Лаодику, и, несмотря на то что наследником считался Митридат, Лаодика согласилась на все требования сенаторов. Именно это и имел в виду Евпатор, когда говорил о том, что «
Пафлагония – это древняя страна в Малой Азии, на побережье Чёрного моря, расположенная между Вифинией, Галатией и Понтом. Пафлагония славилась своими всадниками и со стратегической точки зрения была важнейшей областью региона. Поэтому Митридат и решил начать именно с неё. Проблема заключалась в том, что теперь сенаторы очень внимательно стали следить за тем, что происходит на Востоке, и царю надо было действовать очень тонко. Поразмыслив, Митридат решил отказаться от открытой аннексии Пафлагонии, чтобы соблюсти хотя бы видимость приличий. Также он посчитал целесообразным найти себе в этом деле союзника, чтобы было в случае чего с кем разделить ответственность и выступить единым фронтом против Рима. Таким образом, на сцене появился царь Вифинии Никомед III.
Никомед, как и Митридат, имел свои виды на Пафлагонию. В одиночку он бы никогда не рискнул поживиться за счет соседей, опасаясь вызвать неудовольствие в Риме. Но в союзе с Евпатором Никомед не побоялся проигнорировать мнение сенаторов. Договорившись, два царя начали тихо и неторопливо прибирать к рукам сопредельные их землям территории Пафлагонии. При этом аккуратно подготавливали почву для того, чтобы со временем ввести в города и крепости свои гарнизоны. Посчитав, что нужный момент наступил, в 104 г. до н. э. союзники приступили к решительным действиям. Понтийские и вифинские войска перешли границу и, не встречая организованного сопротивления, разошлись по стране. Таким образом, в период со 107 по 103 г. до н. э. Митридат VI и Никомед III полностью оккупировали земли Пафлагонии. При дележе добычи Митридату достались прибрежные районы вплоть до Гераклеи Понтийской, а Никомеду – внутренние земли.
Это был очередной успех Митридата. Казалось, что всё, за что бы он ни брался, обречено на успех. Однако римские сенаторы, до которых наконец-то дошло, что же происходит в Малой Азии, решили принять ответные меры. К Никомеду III и Митридату VI были отправлены посольства «
Во-первых, потому, что почувствовали, что с той страшной силой, которая появилась на востоке, теперь просто так не справишься. Война с Митридатом потребует длительной и серьезной подготовки. Во-вторых, положение дел в самой Италии и некоторых провинциях внушало квиритам серьезные опасения. Дело в том, что именно в это время началась новая война с рабами на Сицилии (104—99 гг. до н. э.) и успехи восставших не на шутку переполошили сенаторов. Но не это было самое страшное.
В 102 г. до н. э. германское племя кимвров нанесло поражение римской армии, перевалило через Альпы и прорвалось в Северную Италию. Консул Катулл отступил с войсками за реку По и старался не пропустить варваров на южный берег. Над Римом нависла смертельная опасность. Легионы требовались в других местах, и «отцам отечества» стало не до Митридата.