În timpul persecuţiilor împotriva creştinilor, Sfintele Moaşte ale Sfinţilor Mucenici erau de regulă îngropate de credincioşi în locuri ascunse. Aşadar, la Constantinopol, lângă porţile şi turnul cartierului Evghenie, au fost descoperite Sfintele Moaşte ale mai multor Mucenici Sfinţi. Numele lor rămân necunoscute de Biserică.
Când au început să apară minuni şi vindecări în acest loc, s-au aflat Sfintele Moaşte ale Sfinţilor, ele fiind ulterior mutate cu mare cinste, într-o biserică. Unui anume duhovnic, Nicolae Kaligrafos, i s-a descoperit că printre Sfintele Moaşte aflate la Evghenie se găseau şi Sfintele Moaşte ale Sfântului Apostol Andronic din Cei Şaptezeci de Apostoli ai Domnului, şi ale celui dimpreună cu el Iunias (17 mai), pe care Sfântul Apostolul Pavel îi aminteşte în Epistola către Romani (16: 7).
În secolul al XII-lea, o mare biserică a fost ridicată pe locul unde fuseseră descoperite Sfintele Moaşte ale Sfinţilor Mucenici. Această zidire a fost întreprinsă de Împăratul Andronic (1183-1185), al cărei hram era Sfântul Apostol Andronic.