During the times of persecutions against Christians the remains of the holy martyrs usually were buried by believers in hidden places. So also at Constantinople, nearby the gates and tower named the Eugenikoi, were found buried a great number of the bodies of martyrs, the names of which remained unknown by the Church.

When on this spot miracles of healing began to happen, the relics of the saints were discovered and with great honour moved to a church. It was revealed to a certain pious clergyman, Nicholas Kalligraphos, that among the relics discovered at Eugenius were also the relics of the holy Disciple from among the seventy, Andronikos, and his helper Junia, about whom the Apostle Paul makes mention in the Epistle to the Romans (Rom. 16:7).

In the twelfth century at the place of discovery of the relics of the holy martyrs was built a great domed church by the emperor Andronikos (1183-1185), the patron saint of whom was the holy Disciple Andronikos.