The Church of the Taxiarches is located in the Upper Town and seems to date to the 14th century. This is another church whose Byzantine name is unknown. During the period of Turkish rule, the Christians of the area believed that prior to the conquest of Thessaloniki by the Turks, the church honored the name of the Archangels (Taxiarches) Michael and Gabriel. According to the local tradition, a recollection of this double dedication was retained symbolically, in the form of a minaret with a double balcony, when the church was converted into a mosque by Gazi Huseyin Bey in the 16th century, with the name İki Şerife Camii (mosque with two balconies). Then, when the church was restored to Christian worship, after the liberation of the city in 1912, it was dedicated to the Taxiarches. The long period during which the church was used as a mosque produced many modifications to the building, the present form of which is due to a restoration of 1953. 
The church is a two-story structure. The architectural design of the upper story has similarities with that of Hagios Nikolaos Orphanos. Here, too, there is a main timber-roofed hall surrounded on three sides by an ambulatory. The latter has lean-to roofs at a lower level, and ends at the east in two bays that communicate with the sanctuary. The ambulatory is a feature of many 14th century churches in Thessaloniki, and is regarded as a hallmark of the church-building of the city. In its original form, the ambulatory of the church of the Taxiarches will have been open on the west and south sides. The masonry of the church resembles that of Hagios Nikolaos Orphanos, consisting of courses of irregular stone blocks with fragments of brick in the interstices. The exterior faces of the Taxiarches have greater variety, however. The north wall has a plastic articulation consisting of blind arcading and built half-columns, while the east face is enlivened by the mass of the five-sided sanctuary apse, the smaller three-sided apse of the prothesis, and the rich brickwork decoration. 
Internally, the arrangement of the ground-floor corresponds to that of the upper story. The existence of tombs in the form of arcosolia — built-in sarcophagi with arches above them — along the walls, is consistent with the theory that the church was the katholikon of a monastery and that the monks were buried here. 
All that remains of the original painted decoration of the church are the scenes of the Resurrection of Christ and Pentecost on the two pediments. They are difficult to make out today because of the soot that has covered them. The position of the Resurrection on the east pediment, in the area of the sanctuary, was dictated by reasons of doctrine, relating to the mystic interpretation of the Divine Liturgy and referring to the Last Judgment. These wall-paintings made it possible to date the church more closely to the second half of the 14th century.