At the west end of Olymbou Street, near the west city wall and just to the south of the Letaia Gate, stands the Church of the Holy Apostles. The gate to the south of the church and the cistern to the north-west attest that it was the katholikon of a monastery.

The inscription "Patriarch and founder" over the entrance, the monograms on the capitals on the west facade, and the brick inscriptions on the west and south facades refer to Patriarch Niphon I (1310-14) as the founder of the church. A painted inscription on the east wall of the narthex mentions the same patriarch and his disciple Abbot Paul as first and second founder respectively "of this venerable monastery". The depiction of Paul praying before the enthroned Virgin over the entrance to the naos, together with scenes from the Marian cycle in the ambulatory, support the hypothesis that this was a Byzantine monastery dedicated to the Virgin Mary, possibly the Monastery of the Virgin Gorgoepekoos.

The monument is a complex five-domed tetrastyle cross-in-square with a narthex and an ambulatory terminating in two chapels at the east end. The multiple levels which clearly reflect the shape of the cross, the brick-built superstructure, the slender domes, the polygonal bema apses, the arcades, the stepped arches, the demi-colonnettes, the double-light windows, and the triple openings all help to create an elegant, lightsome whole. The decorative brickwork at the east end gives the monument a painterly aspect.

Superb mosaics from Niphon's time survive in a fragmentary state in the highest parts of the naos: the Pantokrator and the prophets in the dome, the evangelists in the pendentives, the twelve Great Feasts in the barrel-vaults and on the west wall, and martyrs of the Church. This was the last mosaic ensemble in Thessaloniki, and one of the last in Byzantium, to be created before the Empire began its decline. Iconographically it has connections with groups from Constantinople, such as the mosaics in the Chora Monastery and the Pammakaristos Monastery; but stylistically the expressive realism that dominates these mosaics reflects the artistic environment which prevailed in Thessaloniki and influenced all of Macedonia during the Palaiologan renaissance. The iconographical programme is supplemented with frescoes of a high artistic standard. The lower parts of the naos, the narthex, the ambulatory, and the north chapel, dedicated to St John the Baptist, are ornamented with scenes from the Old and New Testaments and with symbolic subjects and themes inspired by hymnography. Outstanding works include the Tree of Jesse (a metaphorical image of the genealogy of the Virgin) on the east wall of the south ambulatory, the prefigurations of the Virgin on the north wall of the south ambulatory, the souls of the righteous in the palm of God over the west entrance to the inner narthex, the Christmas hymn "What can we offer you, Christ?" in the north ambulatory, and the life of St John the Baptist in the north chapel. The wall paintings betray a close connection with Constantinople, respiring idealism, delicacy, grace, and serenity, and are closely associated with those of Chora Monastery.
The frescoes are believed to date to the time when Paul, "the second founder", was abbot, after 1314 or between 1328 and 1334.

In around 1520-30 the monastery was converted into a mosque and named the Soguk Su Ҫamii ("mosque of the cold water"). The mosaics and frescoes were plastered over, after the gold tesserae had first been carefully removed. The name "Holy Apostles" is connected with the modern tradition of the nineteenth century.

The wall paintings were uncovered in stages from 1926 onwards. Consolidation work was carried out after the earthquake of 1978. In 2002 the mosaics were cleaned and their rich colours were fully revealed.