The Church of Hagia Aikaterini is just to the west of the Church of Profitis Ilias near the city walls. It is one of the 15 Paleochristian and Byzantine Monuments of Thessaloniki that were included in the UNESCO World Heritage List in 1988.

The elegant Palaiologan church is one of the most 'unknown' churches in the city: its Byzantine name is not known, and the historical sources are particularly scanty in this case.

A good idea of the large number of churches in Byzantine Thessaloniki may be gained from the fact that the surviving Byzantine sources attest to the existence of over fifty churches and forty monasteries, while some Byzantine authors equate the number of churches in the city with the number of days in the year. A mere fifteen have survived to the present day, and the original names are certainly known of only ten of these. The attempt to recognize the Byzantine churches hiding behind the modern names and the Turkish names that preceded them — for the majority of them were converted into mosques — is often as gripping as the plot of a good detective novel: information contained in the Byzantine and Turkish sources has to be combined with the evidence afforded by the monuments themselves and the archaeological excavations conducted on them. What we know of the church of Hagia Aikaterini is that in the reign of Sultan Bayezid II (1481-1512), it was converted into a mosque by the beylerbey Yakup Paşa, to whom it owed its Turkish name (Yakup Pasha Camii). The evidence furnished by the monument itself hints that it may have been dedicated to Christ, and some scholars have therefore identified it with the monastery of Christ the Almighty. 
The church belongs to the same architectural type as the Church of the Holy Apostles, and is a complex tetrastyle cross-in-square church, encircled by a closed ambulatory that ends at the east in two symmetrical chapels. It differs from the church of the Hagioi Apostoloi in having no exonarthex. The facades are pleasantly relieved by blind arcading, brick half-columns and decorative brickwork, while a marble cornice divides the cubic body of the church vertically, creating a strong horizontal axis. A contributing factor to the elegant proportions of the church is the vertical fragmentation of the volumes through the ascending series of roofs, from that over the ambulatory, with the four small domes at the corners, through the curved pediments of the arms of the cross, to the seven-sided dome over the central space. The building is dated by various scholars between the end of the 13th century and the third decade of the 14th. 
During the course of the restoration work carried out on the monument between 1947 and 1951, the painted decoration of the church, which is preserved in fragmentary condition, was also uncovered. The sanctuary apse has scenes of Concelebrating Hierarchs and the Communion of the Apostles; on the main dome, prophets and angels surround the now destroyed Pantokrator; the nave has scenes from the Miracles of Christ, and the west section of the ambulatory is adorned with individual figures of saints, mainly hermits and stylites. Some scholars are of the view that certain elements in the iconographic program suggest that the church was dedicated to Christ. A date of around 1315 has been suggested for these wall-paintings. The lively colors, richly decorated architectural structures depicted, and the tree modeling are the basic features of 14th century art, and link them with the decoration of the Church of Hagios Nikolaos Orphanos and works by the local painters Michael Astrapas and Eutychios, who were commissioned by the Serbian king Milutin.