St. Theodora was the Christian daughter of Maximian (286-305), co-emperor with Diocletian (284-305). She was baptized a Christian by the Bishop of Thessaloniki, St. Alexander (commemorated May 28th), who was later a participant in the First Ecumenical Council. Taking on her new Christian responsibilities, she was troubled by her idolatrous parents, so she told them that she suffered from some sickness, and she as a result sought (for health reasons) to build a house and a bathhouse for herself in the north part of the city. The place was named Latomia because there were stones there that were used to build the church. Immediately after the workers finished the buildings, she converted the bathhouse into a church, under the guidance of the Bishop of Thessaloniki, St. Alexander. She ordered an iconographer to create a mosaic in the eastern apse depicting the Most-Holy Theotokos. When he was finishing the icon, he was struck with amazement, for the next day, the face of the Theotokos no longer appeared, but that of Christ on a light-bearing cloud, surrounded by the four symbols of the Evangelists, and the Prophets Ezekiel and Habbakuk.
This miraculous occurrence the iconographer shared with Theodora, who wanted to keep it a secret. However, one of her servants informed her mother of what had happened. She called Theodora to give an explanation for what had taken place, and also to participate in sacrifice to the goddess Artemis for the salvation of her father Maximian, who was away at war with the Sauromaton. Theodora refused to reveal the existence of the icon and also to sacrifice to the idols. When her father had learned this, he had her locked in prison, where she received a martyr's death. The church that she build was burned, however, the icon remained unharmed, as St. Theodora had previously had it covered with plaster.