The church (Turkish, Meryem Kilisesi), 145 metres long and 30 metres wide, was originally a Roman period basilica built in the 2nd century AD in the southern stoa of a large building complex believed by some historians to have been the Olympieion, the sanctuary of Zeus Olympios (see note on gallery page 21). It was converted into the church of the bishop of Ephesus during the 5th century.

Immediately to the east of the church, remains of a large 5th century building complex have been identified as the bishop's palace (episkopeion). With a length of 140 metres and 30 metres wide, it was almost as large as the church.

The Third Ecumenical Council, also known as the Council of Ephesus, was held in Ephesus in 431 AD during the reign of Emperor Theodosius II, and is thought to have been attended by as many as 250 bishops from several Christian territories. The Council, which may have been held at this building, decided, among other theological issues, on the the title of the Virgin Mary as Theotokos (Greek, Θεοτόκος; literally, God-bearer or Birth-Giver of God), the Mother of God.

This church may have been named in Mary's honour at the Council or soon after, and is thought to have been the first church dedicated to her. It was rebuilt in several phases during the 6th century AD, and numerous times during the late Byzantine period. The variety of columns, capitals and other other architectural members of several styles and periods around the church make it clear that parts of other buildings were brought here over time during the various stages of construction.