В такой ситуации пришедшая к власти политическая группировка искала помощи на стороне у соседнего Боспора и Понтийского царства. Херсонесцы стремились укреплять связи с боспорскими царями для того, чтобы последние воздействовали на дружественных им скифских династов и добились от них прекращения экспансии против Херсонеса. Когда стало очевидно, что достичь этого не удастся, Херсонес пошел на сближение с понтийскими царями, к херсонесцам было отправлено посольство Митридата VI Евпатора. В его задачу входило обговорить условия для заключения нового договора о предоставлении помощи в борьбе со Скифским царством (Страбон, VII, 4, 3; 4). Когда в 110 г. до н.э. скифы оказались совсем близко от города, в Крыму в соответствии с достигнутыми договоренностями появилось понтийское войско во главе с Диофаятом, стратегом Митридата. В ходе войн со скифами, длившихся в течение трех лет, в которых самое деятельное участие принимали и херсонесцы, были взяты царские крепости скифов и их столица Неаполь, освобождена херсонесская аграрная территория в Северо-Западном Крыму вместе с городами Керкинидой и Калос Лименом и разбиты союзники скифов — сарматское племя роксоланов. В Скифии были расквартированы понтийские гарнизоны, а сыновья Скилура, который совместно со старшим сыном Палаком воевал против Митридата, были лишены права на власть над Скифией. Только под давлением Рима Митридат пошел на некоторые уступки, вернув часть владений наследникам Скилура, но и то, назначив в качестве наместников, вероятно, преданных ему людей. За ощутимую помощь в войнах Диофанта Херсонес получил широкие права автономии в рамках созданной Евпатором Причерноморской державы. Об этом свидетельствует некоторое оживление на рубеже II-I вв. до н.э. хозяйственной деятельности усадеб на Гераклейском полуострове и непрекращавшийся процесс чеканки монеты. Город отпал от Митридата только в 60-х годах I в. до н.э., когда почти все греческие города Северного Причерноморья перешли на сторону римлян.
После смерти Митридата Херсонес попал под власть его сына Фарнака (63-47 гг.). После его смерти Юлий Цезарь в 45/44 г. до н.э. предоставил ему свободу. Однако затем город вновь оказался под властью Боспорского царства, когда Асандр вскоре после 42 г. до н.э. сумел, наконец, им завладеть, затратив на это не одну попытку. Херсонес мог подчиняться Асандру на условиях симмахии, добровольного союза, который означал на деле господство более сильного царства над более слабым полисом. Это не исключало, однако, сохранения за Херсонесом прав самоуправления и автономии, что подтверждают его монеты. Ведь город пользовался правами самоуправления как бы неофициально, ибо получил их еще при Асандре, поэтому официально их пришлось подтверждать Августу и Агриппе тотчас после победы при Акции. В 25/24 г. до н.э. были подтверждены его свобода и автономия в рамках союза с Боспорским царством, что ознаменовалось принятием своей городской эры. Херсонесцы поддерживали связи с боспорскими царями Динамией, Полемоном I и Аспургом, и выступили, очевидно, на стороне римлян во время римско-боспорской войны при Митридате VIII.
Важнейший очаг эллинской культуры в Северном Причерноморье — Боспорское царство во второй четверти — середине III в. до н.э. переживало острый финансовый кризис. Это выражалось в постоянных перечеканках и надчеканках монет, а также падении реального веса меди. На ухудшение экономического положения Боспора не могло не повлиять сокращение объема торговых связей с их традиционным партнером Афинами. Это выразилось в прекращении поступления на боспорские рынки афинской керамики, произведений художественного ремесла, терракот. Однако объем вывоза боспорской пшеницы, по крайней мере в первой половине — середине III в. до н.э., вряд ли резко сократился: известно, например, что боспорский царь Спарток III еще в 287 г. до н.э. безвозмездно передал афинянам около 37 тыс. пудов хлеба. И все же боспорская пшеница теперь не пользовалась таким большим спросом, как в V-IV вв.: в период раннего эллинизма было выгоднее закупать зерно в Египте. Изменение соотношения сил в Восточном Средиземноморье после войн диадохов, появление новых торговых центров, таких, как Александрия и Родос, способствовали активизации внешней политики Боспора. В середине III в. до н.э. царь Перисад II направил посольство в Александрию для переговоров с Птолемеем II Филадельфом; тогда же он совершил пожертвование в храм Аполлона на Делосе. Имена боспорских властителей фигурировали в списках жертвователей Аполлону в Дельфах и Дидимах во II в. до н.э. В третьей четверти III в. до н.э. на рынки Боспора активно начинает проникать импорт Родоса, резко возросший в конце III — начале II в. в связи с отменой Византием таможенных пошлин за проезд купцов через проливы после войны с Вифинией и Родосом в 220 г. до н.э.