На другой день Стефан вместе с послами отправился в Константинополь. Император Лев III попытался убедить его отречься от почитания икон. Но Стефан отвечал: "Если ты меня и сожжешь и на части рассечешь, или еще каким-нибудь образом замучаешь, все претерплю за иконы и крест Господень". Разгневанный император приказал бить святителя и заключить в темницу.
После смерти Льва III в 741 г. на престол вступил его сын Константин Копроним. Супруга Константина много слышала о добродетели Стефана и упросила своего мужа отпустить его на Сугдейскую кафедру. В это время у нового императора родился сын, которого, по желанию императрицы, крестил Стефан. Константин, одарив архиепископа, с великой честью отпустил его в Сугдею, где он управлял по-прежнему делами верующих. Почуствовав приближение отшествия к Господу, Стефан поставил вместо себя архипастырем своего клирика Филарета и преставился в жизнь вечную 15 декабря 750 г.
Как добрый пастырь, Стефан прославился даром чудотворения при жизни и по смерти. Один житель города, именем Ефрем, слепой от рождения, которого святой при жизни оделял пищей, питьем и одеждой, услышав о смерти своего благодетеля, воскликнул: "Кто теперь мне поможет? Ведите меня к святителю, я хочу поцеловать ноги его". Когда слепого привели к телу Стефана, он плакал и рыдал - и вдруг прозрел.
Через несколько лет после смерти Стефана пришла в Сугдею великая рать русская из Новгорода во главе с князем Бравлином. Князь спустился побережьем Крыма от Корсуня (Херсона) до Керчи и осадил Сугдею. На одиннадцатый день он ворвался в город и, разбив двери, вошел в храм святой Софии.
На гробе св. Стефана был драгоценный покров и много золотой утвари. Князь Бравлин намеревался схватить покров, но у раки с мощами его внезапно постиг паралич. Тогда он приказал вернуть все похищенное от Корсуня до Керчи, но остался в прежнем положении. Св. Стефан предстал перед ним в видении и произнес: "Если не крестишься в церкви моей, то не выйдешь отсюда".
Преемник св. Стефана Филарет с местным духовенством крестил князя, а затем и его бояр. Бравлин почувствовал облегчение, но полное исцеление получил только после того, как дал обет освободить всех захваченных в Крыму пленных. Внеся богатые пожертвования на храм и почтив своим приветом местное население, Бравлин удалился из Сугдеи.
По мнению исследователей, в "Житии" описывается действительное событие из древней истории. Весьма точно передаются приметы жизни Сугдеи VIII века. Так, храм именуется св. Софией, что точно соответствует действительности. Запись в Синаксаре сообщает об обновлении св. Софии в 793 г., то есть примерно в одно время с опосинным нашествием. Крестил Бравлина преемник Стефана Филарет, который действительно возглавлял тогда Сугдейскую епархию.
При Константине Копрониме в 754 г. в одном из предместий Константинополя состоялся Собор. Он замышлялся как вселенский, но ни Рим, ни Александрия, ни Антиохия на нем не были представлены. Собравшиеся отцы церкви единогласно приняли положение о том, что иконопочитание возникло вследствие козней сатаны. Запрещалось иметь иконы в храмах и частных домах. Все "древопоклонники и костепоклонники", то есть почитавшие мощи святых, предавались анафеме.
После собора 754 г. наиболее решительным противником иконоборчества стало монашество. Это вызвало погромы монастырей. Так, в 770 г. в Эфесе монахам и монахиням предложили на выбор: немедленно вступить в брак и стать светскими лицами или быть ослепленными и изгнанными. Большинство подчинилось и оставило монашескую жизнь, но некоторые предпочли пострадать за веру.
Репрессии вызвали массовую эмиграцию монахов на далекие окраины империи. Как пишет В. Г. Васильевский, "Византия осиротела, как будто все монашество было уведено в плен. Одни отплыли по Евксинскому Понту, иные на остров Кипр, а другие в Старый Рим". Среди эмигрантов, попавших в Крым, были епископы, монахи, пресвитеры, а также мирские люди. Ими были основаны монастыри на горе Аюдаг, в Партените, Панеа в Симеизе, Чилтер-Коба и ряд монастырей вокруг Сугдеи. Иоанн Златоуст писал о людях, селившихся в монастырях за пределами городов: "Избегая городов и народного шума, они предпочли жизнь в горах, которая не имеет ничего общего с настоящей жизнью, не подвержена никаким человеческим превратностям, ни печали житейской, ни порочной любви".
Вокруг Сугдеи строились в основном мелкие обители, в которых проживало нередко от 4 до 10 обитателей. Они не обладали земельной собственностью и жили за счет ремесла, приношений и торговли святыми реликвиями. В одном из поучений Феодора Студита (нач. VIII века) перечислены группы ремесленников, живущих в монастырях: каменщики, плотники, художники, переплетчики книг, кузнецы, гончары, медники. Монахам предоставлялось широкое поле миссионерской проповеднической деятельности среди местного населения. Феодор Студит замечает, что Таврика была убежищем не только ради телесной безопасности, но и для спасения живущих там людей, находящихся во тьме и заблуждении.
В 787 г. в Никее состоялся седьмой Вселенский Собор, на котором иконоборчество было осуждено, а иконоборческие епископы отказались от своих убеждений. На этом закончился первый период иконоборчества в Византии. Представителем Сугдеи на Вселенском Никейском Соборе был епископ Стефан, тезка святого, покровителя города.
Позднее в Сугдее было еще два святых: св. Василий, упомянутый в греческом Синаксаре XIII века (память 9 января), и преподобный Савва, архиепископ Кавказский, скончавшийся в Сугдее, известие о котором помещено на поле греческой минеи XII века (память 2 апреля). Влияние православия на местное население было столь сильным, что многие татары, поселившиеся здесь, стали христианами. Об этом говорят записи в Синаксаре с 1258 г.: "Параскева, татарская христианка" (ум. в 1275 г.); "Иоанна, татарская христианка". Татары принимают даже монашескую схиму.
В XI - XV веках происходит массовое переселение в Крым армян. В одной из армянских рукописей XVIII века сказано: "В то время (в XIV в.) усилились мы и умножились и построили села и округа; князья и знатные люди, начиная от Карасубазара и Феодосии, горы и равнины заполнили церквами и монастырями. И построили мы сто тысяч домов и тысячу церквей и от страха перед гуннами крепостные стены в городе Феодосия".