Во второй половине III в. н. э. в связи с активным наступлением варваров (готского союза племен) на Придунайские римские провинции, Рим вынужден был увести войска из Херсонеса. Но в IV в. здесь вновь базируются отряды римских солдат. Одновременно Рим устанавливает контроль над самыми важными ведомствами городского управления – военным, финансовым и др. В IV в. огромная Римская империя распалась. На ее территории сформировались новые государства с иной формой хозяйства. В восточных областях, принадлежащих рабовладельческому Риму, образовалась крупнейшая феодальная монархия средневековой эпохи – Византия (со столицей в Константинополе). Херсонес входил в состав Византии и в течение многих веков (V–XII вв.) был ее оплотом в Северном Причерноморье (византийцы называли его Херсоном, а русские – Корсунем).
В XIII – XIV вв. кризис Византийской империи и разорительные набеги татаро-монгол (они называли Херсонес Сары-Керман, т. е. Желтая крепость) привели Херсонес к упадку. Еще в начале XV в. в отдельных районах города теплилась жизнь, но к середине этого века Херсонес умирает окончательно. В 1472 г. генуэзскому консулу в Кафе (крепость близ современного города Феодосии в Крыму; по договору с Византией Херсонес в 1350 г. был отдан генуэзцам) сохранилась инструкция: «…было бы полезно снести башни и стены одного необитаемого места, которое называется Херсон. И это в тех целях, чтобы турки не заняли его». Стены и башни необитаемого города не снесли, пустынный и заброшенный он привлекал многих путешественников. В 1578 г. польский посол к крымскому хану Мартин Броневский был в Херсоне и записал в книге своих путешествий: «Город много веков стоит пуст и необитаем и представляет одни развалины и опустошения». К началу первых раскопок руины Херсонеса покрылись землей, заросли травой, кустарником и лишь кое-где выступала кладка крупных строений: оборонительных стен, башен, храмов, крупных жилых домов.
С присоединением Крыма к России (1783 г.) и строительством военного порта Севастополь офицерам флота предписывалось разыскание древностей, описание старинных зданий, зарисовка надписей, составление карт и планов. С конца XVIII в. на херсонесском городище под руководством офицеров русского флота начались бессистемные раскопки, не предусматривающие научного исследования древнего города. В 1827 г., например, работы велись на центральной площади Херсонеса в поисках храма, в котором, как предполагали, мог креститься князь Владимир.
