Крупная греческая колония Ольвия, уже несколько веков располагавшаяся в эстуарии реки Гипанис (Буг), рядом с устьем Борисфена (Днепра), вынуждена была подчиниться скифскому правителю соседнего Крыма, который сам опирался на сарматские племена. Тот же туземный династ угрожал полису Херсонес на юге Крыма (рядом с современным Севастополем) и старому греческому государству, занимавшему берега Боспора Киммерийского (современного Керченского пролива), с его столицей в Пантикапее. Поэтому Херсонес и династ Боспорского царства обратились к Митридату на основании прежних отношений, которые связывали их, и того интереса, который его предки имели к их землям. Царь Понта ответил на их призыв, отправив экспедиционный корпус из 6000 греческих наемников под предводительством стратега Диофанта, уроженца Синопы. Диофант, проведя несколько кампаний (с 110 по 107 год до н. э.), добился замечательных успехов, освободив находившиеся в опасности полисы, заняв большую часть Крыма, включая Боспорское царство, и продвинувшись на континенте до Ольвии; таким образом он объединил весь регион под властью Митридата. Понт получил новую провинцию на другом побережье Черного моря с собственным административным центром в Пантикапее (Керчь), на полуострове, который греки называли Херсонесом Таврическим (Крым). Находясь почти в черноземной зоне русских равнин, эта провинция производила в изобилии зерно, а также серебро, которые были важны для Митридата не менее солдат. Монеты, обнаруженные на месте Ольвии, Херсонеса и Боспорского царства, подтверждают существование в это время тесных экономических связей с анатолийскими владениями Митридата. Это первое приращение, совершенное молодым царем, значительно расширило его возможности. Он постарался продолжить освоение черноморского побережья как к востоку, где он достиг Трапезунта (Трабзона) и Колхиды, так и к западу, где, помня об устремлениях Фарнака в отношении греческих полисов на фракийском побережье, которым угрожали варвары дунайских равнин, установил своего рода протекторат над Аполлонией Понтийской, которая боялась повторить судьбу находившейся севернее Истрии (к югу от устья Дуная), павшей под натиском соседних народов. Таким образом, в последние годы II века до н. э. Митридат стал для Черноморского региона последней надеждой эллинизма перед лицом опасностей, идущих из внутренних земель. Очевидно, что этого правителя с иранским именем воспринимали как греческого царя: именно поэтому впоследствии он был признан греками Малой Азии и старой Греции как освободитель перед угрозой римского завоевания.
Следующий этап плана Митридата состоял в подготовке к неизбежной войне с Римом, для чего ему необходимо было занять выигрышные позиции в Анатолии вокруг Понтийского царства. Тайно посетив римскую провинцию Азию, Митридат убедился, что чужеземная власть вызывает там всеобщую ненависть и что любое смелое выступление способно вылиться в бунт. Действительно, налоговая система, которую ввела в провинции Республика, была похожа на наказание: взиманием налогов (десятиной была обложена вся территория, включая земли греческих полисов, которые до сих пор были освобождены от налогов фискальной политикой Атталидов) занимались римские откупщики, которые при небескорыстном попустительстве правителей обирали страну. Проконсул Квинт Муций Сцевола и его легат Публий Рутилий Руфус в 93 году до н. э. попытались пресечь злоупотребления, но как раз в это время в Риме трибунал, явно благосклонный к обиравшим провинции чиновникам, возбудил против них процесс, в связи с чем они были отозваны из Азии. Митридат, оценив эту взрывоопасную ситуацию, попытался извлечь из нее пользу. С помощью разных маневров он подчинил новые территории, разделив Пафлагонию с вифинским царем Никомедом III, и заключил союз с Тиграном, царем Армении, отдав ему в жены свою дочь. Значительно труднее оказалось разобраться с Каппадокией, где его собственная дочь Лаодика не желала становиться его союзницей: неоднократные попытки подчинить это государство Понту были пресечены римскими военными кампаниями (одна из них была поручена Сулле, который таким образом впервые оказался на Востоке), так же безуспешно Митридат попытался после смерти Никомеда III встать во главе Вифинии. Нового государя этого царства, Никомеда IV, Рим подтолкнул к вторжению в понтийскую Пафлагонию. Это нападение весной 88 года до н. э. развязало войну.