Moaștele Sfântului Întâi Mucenic și Arhidiacon Ștefan au fost descoperite la multă vreme după mucenicia îndurată pentru Hristos, când a fost ucis cu pietre de către iudei în primii ani ai Bisericii creștine.

După ucidere, trupul Sfântului Întâi Mucenic și Arhidiacon Ștefan a stat neîngropat o zi și o noapte, fiind ridicat în ascuns de oameni trimiși de către Gamaliel, conducătorul uneia din principalele școli rabinice ale vremii, care se apropiase de Sfinții Apostoli. A fost înmormântat în satul acestuia, aflat la o oarecare distanță de Ierusalim, fiind pus într-o peșteră, într-un mormânt nou.

Mai târziu, preotul din satul în care a fost îngropat Sfântul, pe nume Luchian, a fost încredințat prin vedenie de către Sfântul Ștefan de locul unde se află îngropate Sfintele Sale Moaște. Luchian a căutat ajutoare, și săpând în acel loc indicat în vedenie, au găsit racla în care erau așezate moaștele Sfântului Întâi Mucenic și Arhidiacon Ștefan. Îndată, patriarhul Ierusalimului împreună cu doi episcopi, cu clerul și cu tot poporul, închinându-se sfintelor moaște, le-au adus la Ierusalim și le-au așezat într-o biserică.

Peste puțină vreme, un mare dregător din Constantinopol, Alexandru, împreună cu soția sa, Iuliana, au venit la Ierusalim. Văzând ei minunile care se făceau de către Sfântul Arhidiacon Ștefan, au zidit în Sfânta Cetate o biserică frumoasă, pe care au închinat-o lui și au mutat sfintele moaște în ea. Când a murit, Alexandru a fost înmormântat lângă Sfântul Ștefan, iar soția sa, dorind să plece în Constantinopol, în loc să ia rămășițele soțului ei, a luat o parte din moaștele Sfântului Întâi Mucenic și Arhidiacon Ștefan.

Când a ajuns la Constantinopol, și-a dat seama de greșeala săvârșită și a i-a dat de veste împăratului și patriarhului bisericii celei mari. Iar aceștia, cu toți preoții din cetate și cu mulțime de credincioși, au mers să ia cu cinste, sfintele moaște și le-au dus în palatul împărătesc; apoi, zidind împăratul o biserică cu hramul Sfântului Întâi Mucenic și Arhidiacon Ștefan, a pus acolo moaștele Sfântului. În timpul domniei Împăratului Teodosie cel Tânăr (408-450), moaștele sale au fost mutate la Constantinopol. Evenimentul este sărbătorit de către Biserica Ortodoxă la data de 2 august. În anul 460, împărăteasa Eudochia a ridicat o splendidă bazilică în afara Porții Damasc a Ierusalimului, locul unde, potrivit tradiției, Sfântul Ștefan suferise martiriul.

În anul 614, sub conducerea lui Khosroes II, perșii au invadat Palestina și au distrus toate bisericile, mai puțin pe aceea a Nașterii Domnului. Astfel s-a pierdut urma bazilicilor închinate Sfântului Ștefan. După cucerirea Constantinopolului de către cruciați în anul 1204, moaștele Sfântului Arhidiacon Ștefan au fost împărțite și au ajuns în diverse locuri.

Astfel, capul Sfântului Arhidiacon Ștefan a fost dus la Soissons în Picardia (Franța), iar picioarele sale la Veneția. Brațul drept al Sfântului Arhidiacon Ștefan se păstrează în Rusia, la Serghiev Posad, în Lavra Sfintei Treimi, întemeiată de Sfântul Serghie de Radonej, în anul 1345. De asemenea, moaște ale Sfântului Ștefan se păstrează în bazilica „San Lorenzo fuori le Mura” din Roma, în Italia și la Mănăstirea Constamonitu din Sfântul Munte Athos unde se află palma dreaptă (primită în dar de la împăratului Teodosie cel Mic).

Săpăturile și cercetările arheologice desfășurate între anii 1883-1885 în apropierea Ierusalimului au scos la iveală o biserică de mărime considerabilă, despre care se crede că ar fi bazilica închinată Sfântului Ștefan de către Împărăteasa Eudochia. În anul 1916, călugării catolici salesieni au identificat locul mormântului Sfântului Ștefan, anticul Kefar-Gamala, cu localitatea Bet Gemal din Țara Sfântă, situată la distanță de 30 de km de Ierusalim, loc unde ei au ridicat și o biserică. În 1999,

Părintele Andrzej Strus, salesian polonez, a descoperit în apropierea noii biserici, la Khirbet Jiljil, un monument care a fost identificat de către unii cercetători cu mormântul Sfântului Ștefan.

În anul data de 22 octombrie 2016, moaștele Sfântului Ștefan au fost aduse din Grecia, pentru închinarea credincioșilor cu prilejul sărbătorii Sfântului Cuvios Dimitrie cel Nou, Ocrotitorul Bucureștilor.