The Great Church of the Theotokos was built in the centre of Byzantine Thessaloniki, to the north of the Leoforos (now Egnatia Street). It was erected on the ruins of a Roman baths complex, traces of which survive inside the church.

It is a three-aisled, timber-roofed basilica with a narthex and galleries. The east end forms a large semicircular apse, to the north of which is a small chapel of the mid-Byzantine period dedicated to St Irene. Beside the south entrance, a structure with an eastern apse is attached to the south wall which was part of the Early Christian basilica.

Two colonnades with superb Corinthian capitals divide the church into three parts. The nave was originally elevated and illuminated by a clerestory, now gone. Access between nave and narthex was through a wide tribelon, and there were single arches between the aisles and the narthex.

The superb mosaics surviving in the soffits of the arches in the colonnades and the galleries, in the two transverse arches in the narthex, in the tribelon, and in the west window all belong to the church's first phase and consist of vegetal and symbolic decorative subjects. On the basis of their style, the style of the sculptural decoration, and the architectural data, the foundation of the church may be dated to the third quarter of the fifth century. The fresco of the Forty Martyrs in the south aisle was painted in the second quarter of the thirteenth century. When Thessaloniki fell to the Ottoman Turks in 1430, Acheiropoietos was the first church to be converted into a mosque by sultan Murad. After Liberation in 1912, it was restored to Christian worship. The earthquake of 1978 caused serious damage to the monument, necessitating extensive restoration, which were funded by the European Union.