Спустя много лет по кончине святого первомученика Стефана посетившая Иерусалим царица Евдокия, супруга греческого императора Феодосия Младшего, построила прекрасную церковь во имя святого архидиакона Стефана в том самом месте, где святой первомученик Христов был некогда побит каменьями, на земле, обагренной его святой кровью.
В IV веке были обретены нетленные мощи святого первомученика Стефана вместе с мощами святого Никодима, святого Гамалиила и сына его святого Авива. Это произошло следующим образом. Однажды пресвитеру Лукиану явился в сонном видении благолепный муж, назвавший себя Гамалиилом, и повелел ему испросить у архиепископа Иерусалимского Иоанна благословение на открытие находящихся в земле мощей святого Стефана, первомученика Христова, а также мощей его, Гамалиила, его сына Авива и святого Никодима. Лукиан, проснувшись, не решился следовать этому видению, не зная, от Бога оно было или нет. Он пребывал в посте и молитве, ожидая указания свыше. После этого Гамалиил снова явился во сне Лукиану и упрекал его, что он не верит ему и медлит исполнить его слово. Так продолжалось до трех раз. Тогда пресвитер поверил видению и, возблагодарив Бога, отправился в Иерусалим к архиепископу Иоанну, которому и рассказал о троекратном своем видении. Архиепископ прослезился от радости и благословил Лукиана отыскать то место, где лежат мощи святых. Возвратившись, Лукиан хотел раскопать находившийся в той местности могильный холм, думая, что там почивают мощи святых; но ночью явился во сне Гамалиил некоему иноку Нугетию и повелел ему сказать Лукиану, что они погребены не здесь, и указал место своего погребения. В указанном Нугетию во сне Гамалиилом месте пресвитер Лукиан стал копать землю и нашел тесный вход в пещеру, в которой и увидел мощи святых. Немедленно он известил об этом архиепископа Иоанна, который с двумя другими епископами поспешил к пещере. Как только открыт был гроб святого первомученика Стефана, земля задрожала, послышалось ангельское пение и благоухание наполнило всю пещеру. Собралось множество народа, и все больные получили исцеление от мощей святого Стефана. После этого мощи святого Стефана были вынесены из пещеры, с почестями перенесены в Иерусалим и положены в церкви при великом торжестве и многочисленном стечении народа. Обретение мощей святого Стефана празднуется Церковью 15 сентября.