Стефан е роден като Стоян Веляновски (Стојан Вељановски) в 1955 година в село Добрушево, Битолско, тогава във Федерална Югославия, днес в Северна Македония. От 1969 година учи в Богословското училище „Свети Климент Охридски“ в Драчево, което завършва в 1974 година. В 1979 година завършва Православния факултет в Белградския университет и Светият синод на МПЦ го назначава за преподавател в семинарията „Свети Климент Охридски“. От 1980 до 1982 година прави магистратура по икуменическа патристика и гръко-византийски изследвания в Института „Свети Николай“ в Бари, Италия. След завръщането си в Югославия преподава в Богословския факултет на Скопския университет Свето писание на Стария Завет и патрология.[1]
Замонашва се на 3 юли 1986 година в охридския манастир „Свети Наум“. След 9 дена, на 12 юли е ръкоположен за Струмишко-Злетовски митрополит в храма „Свети Димитър“ в Скопие.[1] В Щип отслужва панихида за Тодор Александров.
В 1989 година от Злетовско-Струмишката се основават отделно две епархии: Брегалнишката, начело с митрополит Стефан и Струмишката, начело с митрополит Горазд.[2]
В следващите години преподавател в Богословския факултет в Скопие,[1] главен редактор на официалния вестник на МПЦ „Църковен живот“, декан на семинарията „Свети Климент Охридски“ (1991 – 1999) и говорител на Светия Синод на МПЦ.[3]
На 9 октомври 1999 година на Народно-църковния събор в „Света София“ в Охрид е избран за македонски архиепископ. Интронизиран е на следния 10 октомври, като същевременно е и надлежен архиерей на Скопска епархия.[3] Смята се за близък до ВМРО-ДПМНЕ.[4]