In the northwestern part of Ano Poli of Thessaloniki, at the junction of Sachini, Ious and Tsamadou streets, there is an elegant church of the late Byzantine period, that of Agia Aikaterini, the construction of which is placed by the late 13th century until the first decades of the 14th century . This is a complex four-columned registered cruciform church with a closed arcade to the western, southern and northern side, which in the east ends in two symmetrical chapels. In the center of the building, rises a seven-sided dome, and there are four other domes, smaller and lower than the central, one in each of the four corners of the building. A basic feature of the monument is its ornate exterior walls with rich brick jewels. All sides of the church are full of blind arches, small niches, bilova and tribilova openings, brick semi-columns, parapets, cornices, which - combined with the escalation of roofs - break the bulk and create a light and elegant construction.
Inside the church of Agia Aikaterini, there are preserved few fragments of murals, which date back to 1315 and depict the Society of the Apostles, bishops making together the Holy Mass, prophets and angels, scenes of the miracles of Jesus Christ and individual saints, mainly ascetics and stylites. These projects, with their vivid colors and the dynamic figures, which are freely modeled, are remarkable examples of the art of the early 14th century and represent the art of the Palaeologeian era.
The church was originally not dedicated to Agia Aikaterini, but - according to some researchers and based on some elements of its iconographic program – it was built in honor of Jesus Christ, while it is also believed to be the cathedral of the Monastery of Christ Pantodunamos. During the Turkish occupation, at the reign of Sultan Bayezid II (1481-1512), the church was transformed into a mosque and was renamed into Yakup Paşa Mosque, which resulted in gradually oblivion of the byzantine name of the building. With its concession back in Christian worship the monument was connected- without knowning why or on what occasion- with Agia Aikaterini and now it bears her name.