Скилур умер, его сын Палак наследовал его титул, идеи и стремления: основать скифское государство, завладеть Херсонесом, его флотом и, если возможно, то переброситься и на богатый малоазийский берег. В отчаянном положении Херсонес снова настойчиво ищет защиты в Понте; к своим соотечественникам – в Пантикапей – он не обращается, так как последний сам трепещет пред варварами и едва откупается изнурительной данью от Палака.
Херсонес около 115 г. обращается к понтийскому царю Мифрадату VI Евпатору за помощью. Мифрадат быстро отзывается на просьбу и посылает своего талантливого полководца "Диофанта, сына Асклепиодора синопийца", который во главе понтийских и херсонесских войск совершил три больших похода (111-106 г. до Р.Х.), чтобы сломить новое царство скифов.
Об этой борьбе говорит кратко Страбон и довольно подробно псефизм (почетная надпись) в честь Диофанта, написанный на базе его статуи, поставленной ему на акрополе между алтарем Девы и Херсонеса (покровитель народа). Кроме этого Диофант был увенчан золотым венком, и торжественно провозглашено его имя во время религиозного празднества.
В 1-й поход Диофант разбил Палака, "прошел в сердце Скифии и овладел скифскими крепостями Хабами и Неаполисом и подчинил почти всех скифов власти царя Мифрадата, и за это народ, освобожденный от гнета варваров, благоговейно почтил царя достойным образом". После восстания Палака, Диофант снова разбил его, взял прежние города и "отправился в Боспор и соседние с ним места, где убедил и остальных подчиниться". Многие сыновья Скилура подчинились Мифрадату, а Палак и другие ушли в Рим просить защиты. Вскоре скифы завладели Пантикапеем и Феодосией, и Диофант пошел на помощь царю Перисаду Боспорскому, очистил от скифов боспорские города и не успел уйти из Боспора, как Перисад, при возмущении боспорцев во главе о скифом Савмаком против понтийцев, был убит. Диофант подавил восстание, мятежника Савмака отправил в цепях в Синопу, а Боспор объявил подданным царя Мифрадата. С этого времени Мифрадат – царь Боспора и покровитель данника Херсонеса. Итак, Херсонес был спасен от варварского разрушения ценой потери собственной независимости. В Херсонесе помещен понтийский гарнизон, граждане его содержат последний и платят большую дань Мифрадату. В 98-90 г.г. Мифрадат лично усмиряет варваров Тавриды. В 84-3 г.г. Херсонес с другими городами восстал против Мифрадата, но был им усмирен. В 72 г. Херсонес, помогая "матери" своей Гераклее, впервые столкнулся с Римом.
В 66 г. Мифрадат Великий был разбит римским полководцем Помпеем, бежал чрез Кавказ на Боспор и задумал "безумное дело" – сухим путем чрез Дунай пробраться в Италию и Рим, подняв народы южной России и германцев, но измена его любимого сына Фарнака погубила его мечты.
Трагическое самоубийство Мифрадата передало Херсонес в руки римлян.
Нужно заметить, что Мифрадат, подавая помощь Херсонесу, имел в виду и свои выгоды, и опасения. В Херсонесе он имел намерение основать базу для экспорта хлеба в понтийские владения и для комплектования своих войск из варварских областей. Опасения же его касались возрастания могущества скифов; о планах Скилура и Палака относительно южно-черноморского побережья мы уже говорили, а исполнение их угрожало целости и Мифрадатовских владений.
Спасая Херсонес, Мифрадат имел в виду и свою безопасность, победы же над скифами и уничтожение их царства, и слабость греческих колоний дали возможность ему основать свое царство в Тавриде. По смерти Мифрадата VI Херсонесом правит его сын Фарнак I (63-47) (в Понте Фарнак II), который заявил себя вассалом Рима, следовательно, и Херсонес находится в зависимости от Рима. В неудачном восстании Фарнака против Рима принимал участие и Херсонес; после его смерти переходит во владение боспорского царя Асандра (47-17 до Р.Х.).
Боспорские цари притесняют херсонесцев, пытаясь изменить государственный строй. Притесняемые жалуются в Рим. Последний освобождает Херсонес от боспорского царства и, поставив его в ведение наместника Мезии, дарует ему свободу самоуправления, насколько она согласуется с римской программой. Это "освобождение" произошло около 25 г. по Р.Х.
Постепенно римское влияние и сила растут в Херсонесе; здесь, как и в других пунктах (Ай-Тодор основан, вероятно, при Веспасиане (69-79), древнее название Харакс и др.), появляются римские гарнизоны, римские суда заполняют черноморские гавани.
Рим отделяет Херсонес от Боспора и поддерживает его благосостояние с целью ослабить последний. Боспорские же цари становятся в вассальной зависимости от Рима под наблюдением правителя Вифинии. С 46 г. – 134 по Р.Х. Херсонес чеканит свою монету с буквами XEP, а на некоторых слово "свободный".
Около 60 г. по Р.Х. скифы, аланы и др. варвары опустошают Тавриду и грозят Херсонесу, и если бы не Тиберий-Плавт-Эний-Сильван, правитель Мезии, быстро подавивший новое движение с севера, то едва ли устояли бы прежние греческие колонии. Этот шаг римского полководца сделал "свободу" Херсонеса "призрачной".
При Домициане (81-96 по Р.Х.) Херсонес и весь северный Понт остаются без римских войск, отозванных для усмирения вспыхнувшей "дунайской смуты". Боспор снова подчиняет себе Херсонес, а император Адриан (117-138), признавая, что только Боспор в состоянии охранять греческие поселения, передает Херсонес под его власть; он даже усиливает Боспор в ущерб Херсонесу.
В царствование Антонина Пия (138-161) Херсонес свободен от римского гарнизона в союз с Боспором отстаивает независимость от Рима. Союз этот, вероятно, вызван появлением нового народа с севера – готов, которые пред тем покорили алан и, основав "славное царство готов" в Приднепровье, начали наводнять Тавриду. Рим быстро подчиняет Херсонес и намеревается взять все вольности его, которые он называл "свободой"; за сохранение их ходатайствует пред Римом "мать" Херсонеса – Гераклея, с которой, как видимо, Херсонес не порывает связи еще во II в . по Р.Х. К этому времени относится также декрет, данный херсонесцами в честь гераклийца Фрасимеда, сына Фрасимеда, в котором Гераклея называется херсонаситами "мать наша". (Декрет найден, издан и объяснен Р.Х.Лепером в Изв. Имп. Арх. Комиссии).
Скифы и др. племена снова беспокоят Херсонес, и Антонин вынужден ставить в нем большой гарнизон. Херсонес в это время становится главной квартирой для римских черноморских сил сухопутных, и морских.
Отношения между херсонесцами и римским гарнизоном часто оставляют желать лучшего, и нередко херсонесцы жалуются на обиды и бесчинства гарнизонных солдат и офицеров центральному правительству. О последнем говорит одна из надписей I-II в.в. по Р.Х.
Херсонес становится совершенно римской провинцией, а от его самоуправления осталась одна тень. Обеспеченный от внешних врагов, Херсонес интенсивно ведет торговлю, и поднимается экономическое благосостояние его. Сфера же его сношений ограничивается связями с малоазийскими городами. От Марка Аврелия (161-180) до Диоклитиана (284-303) в жизни Херсонеса играют большую роль готы, окончательно погубившие скифов, подчинившие Херсонес и Боспор и уничтожившие всякое значение Феодосии (на время) и Ай-Тодор (навсегда). Херсонес и Боспор – в роли "перевозчиков" готов по берегам Черного моря. Римский гарнизон очистил не только Ай-Тодор, но и остальные пункты, подчиненные Риму. В царствование Диоклитиана, по описанию Константина Багрянородного, происходит ряд событий большой важности для Херсонеса: херсонесцы оказывают императору помощь в борьбе с пантикапейским царем Савроматом и расширяют, будто бы, свои владения до Чатыр-дага, неоднократно занимая Пантикапей.
В царствование Константина I Великого (307-337), по словам того же царственного писателя, Херсонес снова оказывает помощь Риму в борьбе с готами и языгами на дунайской границе под начальством протевона и "носителя венца" Диогена, сына Диогена.
Диоген и сами херсонесцы в благодарность от императора получили разные милости и привилегии.
"Последние годы Константина Великого, говорит историк Херсонеса, были прекрасной порой в политической жизни херсонесцев". Завистливые боспорцы настраивали сарматов против Херсонеса, сами же с трудом удерживались от натиска варваров.
Около 375 г. в Тавриде, оттеснив готов, господами положения становятся гунны.
Во времена Феодосия Великого (379-395), согласно найденной надписи, была построена городская стена при участии трибуна Флавия Вита; в Херсонесе, вероятно, в это время стоял имперский гарнизон. По смерти Феодосия I Херсонес – под властью Византийской империи.
В конце IV в. Херсонес – самое сильное в Тавриде государство. С III в. он называется "Херсон".
Еще в I в. по Р.Х. Плиний Старший (р. 23 – ум. 79) говорит о Херсонесе, как о благоустроенном городе, так: "на самом перешейке полуострова (расположен) Гераклея-Херсонес, которому дарована свобода римлянами; он раньше назывался Мегарикой и был самым блестящим пунктом на всем этом пространстве, благодаря сохранению греческих обычаев; стены его имеют 5,000 шагов в окружности". Писатель того же века и автор "Землеописания" (De Chorographia), Помпоний Мела (около 40 до Р.Х.), говорит о находившейся среди города цитадели. Площади и улицы города отличаются планомерностью, красивыми зданиями с массой украшений статуарной пластики. Хорошо представлены раскопками водопровод и канализация с проложенными гончарными трубами и каналами. Недостаток воды на территории города был во все времена его существования, для устранения его были сделаны водоприемные колодцы, высверленные почти в сплошной известняковой скале (подпочва всего города), куда и стекала дождевая вода; колодцев обнаруживается громадное количества, почти в каждом большом доме был свой. Пользовались также и водопроводом, который давал воду извне стен города. Окрестности города в спокойное время представляли цветущие сады и виноградники.