Росту православного влияния с середины VIII в. способствовала не только миграция монахов, причем многие усматривали в этом миссию, возможность обращения язычников на далеких окраинах, но и то обстоятельство, что Херсон оставался местом ссылки опальных вельмож, в большинстве приверженных православному исповеданию. Новый подъем иконоборчества в первой половине IX в., сопровождавшийся выселением монахов из центральных областей империи на далекие окраины, способствовал росту влияния монастырей в Крыму.
На рубеже 60-х годов славянский просветитель Кирилл, по пути из Хазарии останавливается в городе Фуллы (вероятно, Чуфут-кале), в окрестностях которого проповедует христианство местным язычникам и собственноручно срубает дуб, которому они поклонялись. В Херсоне он предпринимает розыски мощей римского епископа Климента, ученика апостола Петра. Климент был сослан в I в. в Инкерман и за успешную проповедь христианства среди местных жителей по повелению императора Траяна утоплен с якорем на шее. Обретение мощей произошло 30 января 861 г.: они были торжественно перенесены в один из храмов Херсона. Интересна их дальнейшая судьба.
Часть мощей Кирилл увез с собой и подарил их папе римскому в обмен на разрешение продолжать богослужение на славянском языке. Мощи были помещены в церкви св. Климента в Риме, где позднее был похоронен и сам Кирилл. Другая часть мощей, оставшаяся в Херсоне, была увезена в Киев князем Владимиром. Так мощи одного из первых христианских святых были разделены между Востоком и Западом.
В Херсоне же произошло еще одно выдающееся событие: согласно свидетельству его «Жития», Кирилл обнаружил здесь Евангелие и Псалтирь, написанные "русскими письмены", и человека, говорившего по-русски, и скоро сам научился говорить и читать по-русски, а затем сложил свою знаменитую азбуку.[38]
Мнения ученых разделились: большинство исследователей склонялось к тому, что упомянутые "русские письмена" означали готский язык; другие полагали, что речь идет о языке аланов ("роксоланы", "русколаны"); наконец, третьи видели в нем русский язык азово-тмутараканских или киевских русов.
В первой половине IX в. византийское правительство для укрепления своих позиций в Таврике создает Херсонскую фему — особый военно-административный округ во главе со стратигом. В нее входили и крепости в округе Херсона, обозначавшиеся собирательным названием Климаты: Константин Багрянородный в Х в. насчитывал их 9. В XIII в. французский посол к монгольскому хану монах Гильом де Рубрук писал, что между Херсоном и Судаком "существует сорок замков, и почти каждый из них имеет особый язык. Среди них есть и такие, язык которых немецкий.[39]
Видимо, в это число входили крепости всего горного Крыма, включая Южнобережье.Борьба Византии с Русью за причерноморские земли продолжается весь Х век. Русы тревожили Византию набегами в IX в.; в 60-е года часть киевской знати во главе с Аскольдом принимает крещение. Примерно в то же время русы оседают в Приазовье, завладевают Таматархой, позднее называемой Тмутараканью, столицей древнерусского княжества, часть земель которого находилась в Крыму. Походы Святослава в 965 г. окончательно сокрушили Хазарский каганат. Удачный поход Владимира Святославича на Херсон в 988 году расширил русские владения в Крыму. Херсон после долгой осады был взят, но отдан как "вено за жену" — царевну Анну, Русь приняла крещенье — таковы были формы, закрепившие его политический союз с Византией, признавшей, согласно договору, права Руси в Таврике и Приазовье.[40]
В конце XII–XIII вв. нашествие половцев, кочевавших в степях северного Причерноморья, надолго отрезало Русь от крымских земель, уничтожило Тмутараканское княжество. Но немалая часть русского населения удержалась на полуострове. Главным их средоточием стал богатый торговый город Сурож (соврем. Судак). Согласно сообщениям арабского писателя Ибн аль Асира, в конце XII — начале XIII веков в Крыму жило много русских купцов.
Княжество Феодоро