Когда Юстиниан, живший в то время в Херсонесе (нынешний Севастополь), заявил, что вновь собирается царствовать, жители, убоявшись наказания со стороны империи (т. е. Византии), решили либо убить его, либо выслать василевсу (т. е. византийскому императору). А он, проведав об этом, смог спастись бегством и, достигнув Дараса (город в Крыму), потребовал свидания с хаганом (царем) хазар. Узнав об этом, хаган принял Юстиниана с великими почестями и отдал ему в жены Феодору, свою кровную сестру. Спустя некоторое время Юстиниан, отпросившись у хагана, уехал в Фанагорию и жил там с Феодорой. Услышав про это, его враги послали к хагану посла, обещая ему множество даров, если он перешлет им живого Юстиниана. Если же нет, то хотя бы его голову. Хаган уступил такой просьбе и послал Юстиниану охрану под предлогом защиты его от соплеменников, стремящихся устроить против него заговор, а сам приказал Папацу, бывшему его наместником в Фанагории, и Валгицу, архонту Босфора (т. е. хазарскому наместнику района Керченского пролива), убить Юстиниана, как только им подадут знак. Но так как через слугу хагана об этом была извещена Феодора, все стало известно и Юстиниану. Призвав упомянутого Папаца для беседы наедине, он задушил его струной. Так же поступил Юстиниан и с архонтом Валгицем. Затем он немедленно отсылает Феодору в Хазарию, а сам, тайно сбежав из Фанагории, прибыл в Томы (местность в Крыму). Найдя там снаряженную гелиаду (рыбацкое судно), Юстиниан договорился с владельцем, погрузился на нее и доплыл до Херсона, а оттуда, минуя устье Днепра и Днестра, вошел в реку Дунай. После этого он послал своего соратника к Тервелю, царю Болгарии, с тем, чтобы он дал помощь для овладения империей своих предков. Затем с помощью болгар и славинов он захватил Константинополь и провозгласил себя императором.
В VII в. Фанагория была столицей Великой Болгарии. Именно отсюда начался поход на Дунай хана Аспаруха, основателя современной Болгарии. В городе существовали одни из самых древних общин христиан и иудеев, что зафиксировано письменными документами и археологическими материалами. В частности, фанагорийская синагога является одной из самых древних в Причерноморье (известна по надписи 51 г.).
Херсонес в Севастополе — греческая колония
Херсонес был греческой колонией, основанной в 422–421 гг. до н. э. выходцами из Гераклеи Понтийской. Он расположен в юго-западной части Крыма, у бухты, которая в настоящее время называется Карантинной. В переводе с греческого «Херсонес» означает полуостров. Здесь жили земледельцы и ремесленники, врачи и скульпторы, архитекторы и художники, историки и поэты. Это была рабовладельческая республика с демократической формой правления. Высшим органом государственной власти являлось народное собрание. Все годы существования государства херсонеситам приходилось вести войны. Во II в. до н. э. шла кровопролитная, длительная война со скифами. Херсонес Таврический вынужден был обратиться за помощью к понтийскому царю Митридату VI Евпатору, который направил в Крым большой отряд во главе с полководцем Диофантом. Скифы были разгромлены, однако и Херсонесу не удалось сохранить свою самостоятельность: он вошел в состав державы Митридата. С тех пор город находился в постоянной зависимости от своих более сильных соседей.
В I в. до н. э. Херсонес утратил демократическую форму правления, попал в зависимость от Римской империи и долго служил основным форпостом ее на рубежах в Северном Причерноморье.
С началом новой эры в Херсонес проникает христианство, в IV в. оно становится официальной религией. Безжалостно разрушаются памятники античного искусства, театр, храмы, их заменяют христианские церкви, часовни. В этот период от нашествия гуннов погибают многие города. Херсонес, защищенный мощными оборонительными стенами, продолжает жить еще тысячелетие, но уже в условиях нового, феодального строя.
В V в. Херсонес вошел в состав Византийской империи, а в IX в. стал одной из ее военно-административных областей. К этому времени изменился не только внешний облик средневекового города, но и его имя: византийцы называли его Херсоном, славяне — Корсунем.