Скифам срочно требовался выход к морю в районе Херсонеса, откуда можно было быстро и сравнительно безопасно пересекать море вдали от пиратских берегов. Теснимые скифами, херсонесцы при посредничестве римлян заключают в 179 году до н. э. договор о помощи с шестым царем династии Митридатидов Фарнаком. Скифы отступились. Они выжидали.
Их час настал семьдесят лет спустя. Скифский царь Скилур вступил в соглашение с сарматским племенем роксоланов, обитавшим в междуречье Танаиса и Борисфена, и стал тревожить границы Херсонеса, а заодно и Боспора, решив попытать счастья на берегах Меотиды. Афиняне уже ничем не могли помочь Боспору; Греция стала римской провинцией. И тогда боспорский царь Перисад V последовал примеру херсонесцев: он обратился за помощью к Митридату VI. Одновременно в Понт с той же целью вторично отправили послов херсонесцы. Херсонес, по словам Страбона, «прежде был самостоятельным, но, подвергаясь разорению варварами, был вынужден выбрать себе покровителя в лице Митридата Евпатора; последний хотел стать во главе варваров, обитавших за перешейком (Перекопом) вплоть до Борисфена и Адрии. Это были приготовления к походу на римлян. Итак, Митридат, окрыленный такими надеждами, с радостью послал войско против Херсонеса и одновременно начал войну со скифами, не только со Скилуром, но также и с сыновьями последнего - Палаком и прочими (их, по словам Посидония, было 50, а по Аполлониду - 80). В то же время Митридату удалось всех их подчинить силой и стать владыкой Боспора, получив эту область добровольно от владевшего ею Перисада. С тех пор и до настоящего времени город херсонесцев подчинен властителям Боспора».
Протекторат Митридата, однако, не пришелся по вкусу ни боспорцам, ни скифам. Перисад отрекся от престола в его пользу, но поскольку понтийский царь был еще далеко, скифский царевич Савмак, приемыш Перисада, убил своего благодетеля и взбунтовал скифских рабов в Пантикапее. К ним присоединилась часть армии и флота; наместник Митридата Диофант спасся бегством на присланном из Херсонеса судне. Савмак принял царский венец и носил его около года: в 106 году до н. э. Диофант вернулся с войсками, захватил с помощью херсонесцев Феодосию и Пантикапей, взял Савмака в плен и передал Боспорское царство Митридату.
Примерно в это же время Митридат подчинил Колхиду. Единственным автономным городом в этой стране осталась Диоскурия, и это наводит на мысль, что она оказала Понту какую-то важную услугу - быть может, попросила Митридата о защите, как Херсонес и Бос- пор, или помогла ему в покорении местных племен.