Позже город попал под зависимость Византии. В это время также ведется крупное строительство, возникают многие новые поселение за стенами крепости, еще больше отстраивается морской торговый порт.
В средние века Херсонес продолжал процветать и стал известным на Руси, где его называли Корсунь. Прекратил свое существование Херсонес только в XIV веке, простояв почти тысячу и исчезнув последним из античных городов Северного Причерноморья.
Таким образом, сооружения крупнейшего города-порта древнего мира Херсонеса Таврического стоят на восточном берегу Крымского полуострова уже более 2500 лет. Руины древнегреческих, древнеримских и византийских улиц, площадей и домов рыбаков и торговцев, складов и магазинов, храмов-базилик детально изучены, описаны и датированы. Их местонахождение, ориентирование, принадлежность ни у кого никаких сомнений не вызывает.
А вот в отношении оборонительных сооружений Херсонеса споры не затихают уже десятки лет. Непонятным представляется то, что расположение трех рядов крепостных стен города, подробная датировка которых дана одним из бывших директоров Херсонесского музея-заповедника И.Антоновой, противоречит имеющимся представлениям о наступлении моря на сушу. Дело в том, что самые старые крепостные стены стоят далеко от современного берега, а более молодые подходят к самому морю.
Это кажется по меньшей мере странным. Ведь известно, что одним из самых уязвимых и ответственных районов древнего приморского города был его порт, который и защищался от врагов, нападавших со стороны моря, толстыми каменными стенами. По устоявшимся правилам античной и средневековой портовой фортификации оборонительные стены обычно строились у самой воды, что давало возможность отгонять вражеские корабли от города. Поэтому построенные в разное время ряды крепостных сооружений Херсонеса, несомненно, должны отмечать и границу «суша — море». А если так, то остается признать удивительный факт: 3 раза перестраивавшаяся крепость Херсонеса следовала за отступавшим урезом воды и, следовательно, море не наступало на берег, как считалось раньше, а, наоборот, отступало.
В этом и состоит парадокс Херсонеса, отмеченный рядом исследователей, сопоставлявших результаты херсонесских измерений с такими же наблюдениями в Ольвии (устье Днепра), Фанагории (Таманский залив) и других местах Причерноморья. В итоге всеобщее признание получило мнение, что херсонесский феномен вовсе не исключение из правил, а подтверждение высказанного еще раньше предположения о всеобщем понижении уровня Черного моря в XIV–XV веках. Этот процесс даже получил херсонесское название: корсунское отступление моря.
