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