The Church of the Holy Apostles rises on the south side at the beginning of Ayiou Dimitriou Street, which coincides with the site of the Letaia Gate. Once the katholikon of a monastery, it owes its modern name to the popular belief that the church was once roofed with twelve domes symbolizing the apostles. In all probability, however, the katholikon was dedicated to the Virgin, as is attested by the repertoire of the wall-paintings in the ambulatory of the church, and the portrayal of its second founder along with the Virgin.

The monastery was founded in the period 1310-1314, with a grant from the Patriarch Niphon I. His contribution is immortalized by three inscriptions in the church that record his name, his office and the fact that he was the church's founder. The first of these inscriptions is inscribed on the marble lintel of the west entrance. The second, which takes the form of a series of monograms, is recorded on the impost blocks of three capitals on the west façade. The third also takes the form of ligatures, worked this time in brick, on the west and south fronts of the church.

The second founder of the monastery is recorded as being the Abbot Pavlos, a pupil of Niphon, who is immortalized kneeling before the enthroned Virgin and Child in the scene on the east wall of the narthex, above the Royal Door. His identity and his connection with Niphon are recorded in the inscription accompanying the scene. Between the years 1520 and 1530 the church was converted into a mosque by Cezeri Kasım Pasha, after whom it was named. It was also known as Soğuk Su Camii ('cold water mosque'), however, from the cistern next to it.

The surviving parts of the monastery complex include, in addition to the katholikon, a portal to the south-west and a cistern to the north-west. When one considers that a single dimension of the courtyard — that between the portal and the cistern — measured 115 m, it is clear that the monastery occupied a considerable area. The importance of this patriarchal foundation is attested not only by its great size, but also by the brilliance of the architecture and interior decoration of the katholikon, and the size and careful construction of the other buildings. The portal, of which two arches now survive, was an imposing, tower-like building. The capacity of the large cistern, which has careful masonry with decorative brick-work on the south face, suggests that it will have been used by a large number of monks, and points to the wealth of the monastery.

The katholikon belongs to the type of the complex tetrastyle cross-in-square church with a narthex and ambulatory on three sides. The ambulatory ends at the east in chapels and is roofed with four small domes at the corners, the two at the west end of the church being folded internally. The east face is dominated by the large, seven-sided sanctuary apse, flanked by the smaller three-sided apses of the prothesis and diakonikon.

The building has very harmonious proportions, its facades are relieved by blind arcading and brick half-columns, and there is some very rich decorative brick-work, especially on the east face. The inside of the nave is copiously lit by large triple-light windows in the drums at the ends of the arms of the cross, and the windows in the main, ten-sided dome. The large number of openings gives the domes a pierced, light appearance. The elegance of the building extended also to the original curved cornice that encircled the cubic base of the monument, following the undulations of the arches. This cornice was replaced in the period of Turkish domination by the present straight one. At this same period, the church underwent other modifications, the most important being the blocking of the tribela of the esonarthex and the demolition of the campanile in front of the west entrance.

The brilliant — even in its present fragmentary condition — mosaic decoration of the church was executed thanks to a grant from the Patriarch Niphon, for works of this kind were very costly. The Patriarch's intention was to decorate the upper part of the church with mosaics and the lower part with marble revetment, presumably in imitation of churches in Constantinople, particularly the Chora Monastery, which he seems to have used as a model. His removal from the patriarchal throne in 1314, however, prevented him from bringing his ambitious project to completion, and the mosaic decoration was confined to those parts of the nave above the level of the cornice.

On the main dome, the mosaics depict the Pantokrator in bust, surrounded by ten full-length prophets. Lower down, the pendentives have portrayals of the four evangelists, with the Hagion Mandelion amongst them at the base of the dome. Scenes from the Dodekaorton are preserved on the vaults over the arms of the cross, on two arches, and on the west wall. The Nativity and Baptism are depicted on the south vault of the cross, the Transfiguration and the Entry into Jerusalem on the west, the Descent into Hell and the Crucifixion on the north, and a small part of the Annunciation and the Presentation of Christ in the Temple can be made out above the arches linking the north-east column with the north wall and the south-west column with the south wall respectively. On the west wall is preserved part of the Dormition of the Virgin, and ten full-length figures of saints are depicted in the west part of the church, with the busts of two more saints above the three-light window on the north side.

The mosaics of the Holy Apostles —one of the last examples of this kind of decoration in the Byzantine Empire — are, along with the corresponding depictions in the Chora Monastery and the Church of the Pammakaristos in Constantinople, the supreme examples of the art of the Palaiologan period. Their strong recollections of Hellenistic elements, discernible in the treatment of the bodies and clothes, their rendering of feelings in the faces, and their tendency towards realism are all features distinguishing them from the idealistic works in the capital. The wall-paintings completing the decoration of the katholikon are of equally high quality. They were inspired by the Abbot Pavlos, who followed the iconographic program laid down by the Patriarch Niphon, as is clear from the unity of concept of the decoration as a whole. The apse and vault of the sanctuary are left undecorated.

The lower parts of the walls of the sanctuary, the nave, the ambulatory and the esonarthex were adorned with figures of hierarchs and deacons, hermits, martyrs and military saints. The upper parts of the walls of the ambulatory and the esonarthex have scenes from the Old and New Testaments, from the lives of the Virgin and St. John the Baptist, the martyrdom of Saint Demetrios, and the Forty Martyrs, as well as scenes inspired by the texts of hymns.

On the cast wall of the south section of the ambulatory, the outstanding scene is that of the Tree of Jesse, referring to the family tree of the Virgin. The scenes from the Old Testament chosen to decorate this same area again have reference to the Virgin, being prefigurations of her. Scenes from the Birth and childhood of the Virgin are also painted on the esonarthex. Here, the finest compositions are that above the west entrance depicting the hand of God holding the souls of the righteous asleep, in the form of babies wrapped in swaddling clothes, and the depiction directly opposite, above the Royal Door to the nave, the enthroned Virgin and Child with two Angels, with the abbot Pavlos falling it her feet.

The west and north sections of the peristyle were decorated with episodes from the gospels. The outstanding scene on the south wall of the north section is the visual rendering of a hymn sung on Christmas Eve, which is again connected with the Virgin. The north chapel, dedicated to St. John the Baptist, was painted with scenes from his life, of which the finest are Herod's Feast with the Dance of Salome on the north wall, and the Birth of St. John opposite. The small dome covering this area has scenes of the Virgin, in bust, holding Christ at her bosom, flanked by angels, portrayed both full-length and in medallions. These scenes are highly impressive for their sensitivity to color, the quality of the faces, the harmony of the proportions and the precision of the execution. These wall-paintings have only been uncovered in recent years.

The two small domes at the west are dominated by the figure of Christ in bust at the top, flanked by hosts of Angels and prophets.