The church is located in the upper quarter of the old city, and dates to the Palaiologan period, but its original dedication is unknown. In Ottoman times, it was known as the Saraylı Mosque, and through a misinterpretation of this name came about its modern dedication to the Prophet Elijah. It has been traditionally identified as the katholikon of the Nea Moni monastery, built ca. 1360–1370 on the site of a former palace destroyed in 1342 by the Zealot uprising. Modern research however has cast doubt on this, since the Nea Moni continued to operate well into the Ottoman period, while the church of Prophet Elijah was converted into a mosque by Badrah Mustafa Pasha immediately after the city's capture in 1430. On the basis of its internal decoration, it has been suggested that the church was the katholikon of the important Akapniou Monastery.
Its architectural style, a variant of cross-in-square church known as the "Athonite type", is unique in the city, and was always reserved for katholika of monasteries. The careful masonry, of alternating courses of bricks and white ashlar, is also unusual for Thessaloniki and its region; it is copied from Constantinopolitan architecture. Fragments of the church's original decoration survive in the form of wall paintings, fine examples of late Palaiologan art, which influenced later paintings in Serbia.