În timpul persecuțiilor asupra creștinilor, rămășițele sfinților martiri erau îngropate de credincioși în locuri ascunse. În Constantinopol, aproape de porțile și turnul cunoscut sub numele de Porțile Eugenie, au fost îngropate multe trupuri de martiri, ale căror nume au rămas necunoscute Bisericii. Când au început să aibă loc minuni de vindecare în acest loc, moaștele sfinților au fost descoperite și cu mare cinste au fost transferate în biserică. A fost descoperit piosului cleric Nicolae Caligraful că printre moaștele găsite în Eugenie se află moaștele sfântului apostol din cei șaptezeci, Andronic, și ale ajutoarei sale Iunia, menționate de sfântul apostol Pavel în Epistola sa către Romani (Romani 16:7). În secolul al XII-lea, pe locul descoperirii moaștelor sfinților martiri a fost construit un templu magnific de către împăratul Andronic (1183–1185), al cărui înger era sfântul apostol Andronic.
