Проте вдячні херсонці поставили на громадському місці дві мідні статуї на честь Глікії, на одній з яких вона була зображена скромно одягненою, приймаючи депутатів міста; а в іншому, одягнений у військовий одяг, в акті помсти зрадженим громадянам.
За часів Візантійської імперії Херсон час від часу брав участь у постійних революціях у Константинополі та у війнах між росіянами та грецькими імператорами. Довго в а.д. 988 р. руський князь Володимир, ідолопоклонник, обложив Херсон і вклав його на сушу. Мешканці чинили впертий опір і знищували споруди обложників так само швидко, як вони продовжувалися; доки Володимир, зрадою повідомлений про джерела, що постачали місто, не перерізав труби і не змусив гарнізон здатися через спрагу. Володимир дав обітницю, що якщо розповідь про джерела виявиться вірною, він стане християнином, і тому був охрещений у Херсоні в церкві Пресвятої Богородиці, що стояла на базарі. Раніше він вимагав від грецьких імператорів Василя і Костянтина руки їхньої сестри Анни; вінчання відбулося відразу після хрещення, а місто Херсон було передано греками як посаг княгині. Повернувшись до Києва, Володимир змусив свій народ прийняти його новоприйняту релігію, і цим періодом датується навернення руського народу до християнства.
Херсон був повністю зруйнований після 2000 років існування Ольгердом, литовським завойовником Києва та всієї південної Русі; а коли турки в 1475 році заволоділи Кримом, вони знайшли в Херсоні лише порожні будинки та запустілі церкви. І все-таки, коли Броновій наприкінці шістнадцятого століття відвідав це «горде, витончене та славетне місто», як він його називає, руїни навіть тоді були чудовими. Стіна та її вежі, побудовані з величезних блоків тесаного каменю, були досконалими, а красивий акведук ще привезли найчистішу воду. Палац царів, великий, як місто, з чудовими в’їзними воротами, продовжував існувати. Однак у церков турки вже позбавили найкращого мармуру, і найбільший грецький монастир залишився цілим. Роботу руйнування завершили татари і росіяни, які шукали тут матеріалів для будівництва Севастополя. Проте минулих віків і вандалізму послідовних варварських рас не вистачило, щоб повністю знищити останні сліди стародавньої пишності. Лейтенант Крузе розкопав три церкви; один із них був видатний тим, що, очевидно, був прекрасним грецьким храмом, який перетворився на християнську церкву, у стіни якої були вбудовані бази та капітелі іонічних колон та інших частин грецької архітектури. Мис, на якому нині стоїть Маяк, повністю вкритий руїнами першого Херсона, а весь Гераклеатичний Херсонес усіяний залишками вілл і садів, що належали мешканцям міста.