Римляне поручили ведение войны в первую очередь консулу 680 г. [74 г.] Луцию Лукуллу. В качестве наместника Азии и Киликии он был поставлен во главе находившихся в Малой Азии четырех легионов, а также пятого, доставленного им из Италии; с этой армией, состоявшей из 30 тыс. человек пехоты и 1 600 всадников, он должен был через Фригию вторгнуться в Понтийское царство. Коллега его Марк Котта с флотом и другим римским отрядом двинулся в Пропонтиду, чтобы прикрыть провинцию Азию и Вифинию. Наконец, было постановлено вооружить все берега, в особенности фракийский, которому прежде всего угрожал понтийский флот, а очистка всех морей и берегов от пиратов и их понтийских союзников в исключительном порядке была поручена одному магистрату, причем для этого был избран претор Марк Антоний, отец которого 30 лет назад впервые проучил киликийских корсаров. Помимо того, сенат предоставил в распоряжение Лукулла 72 млн. сестерциев на постройку флота, от чего, однако, Лукулл отказался. Как видно из всего этого, римское правительство поняло, что корень зла лежит в отсутствии внимания к флоту, и приняло против этого серьезные меры, по крайней мере насколько имели силу его декреты.
Итак, в 680 г. [74 г.] война началась во всех пунктах. Несчастьем для Митрадата было то, что как раз в момент объявления им войны наступил поворот в серторианской войне, вследствие чего сразу же рухнула одна из главнейших его надежд, а римское правительство могло направить все свои силы на морскую и малоазийскую войну. Зато в Малой Азии Митрадат использовал преимущества наступления и большую отдаленность римлян от непосредственного театра войны. Большое число малоазийских городов открыло свои ворота серторианскому пропретору, командовавшему в римской провинции Азии, а проживавшие там римские семьи были, так же как в 666 г. [88 г.], перебиты; писиды, исавры, киликийцы поднялись против римлян. В тот момент в угрожаемых пунктах не было римских войск. Правда, отдельные энергичные люди пытались своими силами положить конец этим волнениям провинциалов. Так, молодой Гай Цезарь, узнав об этих событиях, покинул Родос, где он находился для научных занятий, и с наскоро составленным отрядом отправился против мятежников; но такие партизанские части не могли сделать многого. Если бы храбрый Дейотар, один из тетрархов проживавшего возле Пессинунта кельтского племени толистобогов, не стал на сторону римлян, успешно сражаясь с понтийскими полководцами, то Лукуллу пришлось бы прежде всего отнимать у противника внутреннюю часть римской провинции. Но и так драгоценное время ушло на успокоение страны и оттеснение неприятеля, и эта потеря времени нисколько не искупалась незначительными успехами, достигнутыми конницей Лукулла.