Büyük İskender dönemiyle birlikte, Anadolu’da İran egemenliğine son verilmesinin ardından bir çok yeni siyasi oluşum ortaya çıkmış, çoğu İran kökenli eski valiler, kendilerini bulundukları bölgelerin kralları olarak ilan etmişlerdi. Bunlardan biri de, “Karadeniz Kapadokyası” olarak bilinen bölgede, Amasya kentini kendilerine yönetim merkezi olarak seçen, İran menşeli Mithridat hanedanıdır.70 MÖ. 114 yılında iktidara gelen VI. Mithridat Eupator’un saltanatı sırasında en parlak çağını yaşayan Mithridat Krallığı71, aynı yıllarda, başkentini önce Amasya’dan Sinop’a taşımış, sonraki yıllarda, egemenlik alanı Trakya ve Yunanistan’a doğru genişlediğinde de, Ege sahillerindeki Bergama kentini yeni yönetim merkezi olarak belirlemiştir. MÖ. 110 yılına doğru, Trapezos kentininin yanısıra, Kolha ülkesini de egemenliği altına alan Mithridat, bu ülkeyi valileri aracılığıyla yönetmeye başlamıştır. Mithridat egemenliğinde Kolha ülkesinin durumu ile ilgili bilgiler oldukça yetersiz olmakla birlikte, MÖ. 83 yılında, Kolhalıların ayaklanması ve valinin değiştirilmesi talebinde bulunmaları, bu dönemde, bölgeye ilişkin tarihsel kayıtlarda yer almaktadır. 72
MÖ. 65 yılında Romalılara karşı yürüttüğü savaşı kesin olarak kaybeden ve Anadolu’daki egemenliğinden vazgeçmek zorunda kalan Mithridat, son çare olarak Kırım bölgesindeki topraklarına giderek, hükümranlığını orada sürdürmeye karar verir. Bu yolculuğunda, Roma donanmasının Karadenizdeki varlığı nedeniyle, kara yolunu tercih eder ve Karadeniz’in doğusundan, Kolha ülkesi toprakları üzerinden geçerek, Kırım bölgesine ulaşır. Onun bu maceralı yolculuğu ile ilgili olarak aktarılan rivayetlerde, özellikle Kolha’nın kuzeyindeki sahillerde karşılaştığı yerli kabilelere ve onlarla olan ilşkilerine de değinilir;
“…Mithridat’ın, kendi ülkesini terk edip, Bosphorus’a kaçtığı dönemde Heniohi’lerin dört kralı vardı. Mithridat, onların ülkesinden herhangi bir engelleme ile karşılaşmadan geçebilmiş; ancak Zygi kabilesinin topraklarından geçerken, bu memleketin engebeli, sarp arazisi ve sakinlerinin vahşiliği nedeniyle, yolun büyük bir kısmında ancak denizin kenarından yürüyerek ileryebilmiş, Akhai topraklarına zorlukla ulaşabilmişti.” Strabon (11.2.13) 73
