Святитель Стефан был родом из Каппадокии (Малая Азия), 15-ти лет пришел в Царьград для высшего образования, которое и окончил успешно, так что превзошел «всех учителей, иже во граде». Все удивлялись усердию, выдающимся способностям и смирению юноши. Благонравие Стефана было замечено святым патриархом Константинопольским Германом I (715-730; † 740; память 12/25 мая). Несколько лет святой Стефан жил со святителем и служил в Константинопольской церкви, а затем тайно ушел в один из монастырей и там принял монашеский постриг. Вскоре он, стремясь к безмолвию, поселился в пустынном месте, где провел несколько лет в подвигах поста и молитвы.

Около 730 года в городе Суроже (ныне город Судак в Крыму) умер епископ. В этом большом торговом городе жили люди разных вероисповеданий. Среди них было много язычников и магометан. Христиане Сурожа просили патриарха Германа прислать епископа, который бы упрочил Православие. Во время молитвы патриарху явился Ангел и сказал, что епископом должен быть святой пустынник Стефан. Воля Господня была открыта также и Стефану. Вскоре он был рукоположен во епископа и отплыл в свою епархию.

Пять лет святитель Стефан провел в неустанных пастырских трудах, просвещая народ словом истины. В результате многие иноверцы Сурожской епархии были присоединены к Церкви Христовой.

В то время византийский император Лев III Исавр (717-741) приказал хулить и бесчестить иконы. Он сместил патриарха Германа, отказавшегося присоединиться к иконоборцам, и поставил на его место сирианина Анастасия, который пробыл на патриаршей кафедре с 730 по 753 год. Святитель Стефан прибыл в Константинополь и обличил императора в иконоборчестве. Лев Исавр пытался уговорами и угрозами склонить святителя к иконоборческой ереси, но безуспешно. Святой Стефан отвечал императору: «Хотя бы ты меня сжег или рассек на части, за иконы и Крест Господень все готов претерпеть». За свою ревность он был жестоко избит, а затем на многие годы заключен темницу.

В 741 году умер император Лев III и на престол вступил его сын Константин V Копроним (741-775). Он также был иконоборцем. Но по ходатайству жены императора Ирины святитель Стефан был освобожден и возвращен на свою кафедру.

Святителю Стефану, уже глубокому старцу, было открыто время его кончины. Он назначил себе преемником клирика Филарета и мирно преставился ко Господу.

Сохранилось свидетельство, что в начале IX века русский князь Бравлин во время похода в Крым принял крещение, обратившись к истинной вере под влиянием чудес у раки святителя.

Яко святитель со Бесплотными единожитель быв, священномучениче Стефане, восприим бо Крест яко оружие, и став крепко сопротив иконоукорителя и духоборцев, не покланяющихся пречистому образу Христа Бога нашего, и отсекл еси всяку ересь лукавых. Того ради прием мучения венец, избавил еси град твой Сурож от всякия неприязни. И ныне молим тя, святе, да избавиши нас от всяких злых искушений, и бед, и вечныя муки.

Вышняго силою, священне, укрепився, царева низложил еси иконоборная шатания; днесь Сурожу и нам верным предлежат слава и богатство — святыя твоя мощи, ихже свыше дароносят ангельстии чинове, песньми и пением славословят тя, великий священный Стефане.