Η εκκλησία του Τιμίου Σταυρού στο χωριό Παλιόμυλος έχει υποστεί δυο καταστροφικές επεμβάσεις το 1881 και στη δεκαετία του 1940. Στην πρώτη επέμβαση, που ήταν εξαιρετικά καταστροφική, κατεδαφίσθηκαν ο νότιος και ο δυτικός τοίχος με αποτέλεσμα να χαθούν για πάντα οι τοιχογραφίες που τους διακοσμούσαν. Σήμερα η εκκλησία είναι δίκλιτη κι έχει ακανόνιστο ορθογώνιο σχήμα με προεξοχές στα νότια και στα δυτικά. Οι εσωτερικές διαστάσεις, χωρίς την αψίδα και τη νότια προεξοχή, είναι 11,15X5,92 μ. Η αψίδα είναι ημικυκλική κι έχει χορδή 1,44 μ. και βέλος 0,74. Τα δυο κλίτη της εκκλησίας χωρίζονται από ένα πάσσαλο, πίσω από το εικονοστάσιο, και τρεις κτιστές κολόνες που στηρίζουν ξύλινο επιστύλιο.
Οι τοίχοι της αρχικής εκκλησίας κτίσθηκαν με ακατέργαστους λίθους και λάσπη και έχουν πάχος 0,60 - 0,65 μ. Οι τοίχοι της νότιας και της δυτικής επέκτασης, που έγινε το 1881, κτίσθηκαν με τα ίδια υλικά αλλά έχουν πάχος 0,53 μ. Το ίδιο πάχος έχουν και οι τοίχοι της νεότερης επέκτασης αλλά είναι κτισμένοι με τσιμεντοπηλό.
Από την αρχική εκκλησία σώζονται ο βόρειος τοίχος και ο ανατολικός τοίχος με την αψίδα. Οι αρχικές διαστάσεις της εκκλησίας ήσαν 7,20X3,05 μ. Κατά την επέκταση της εκκλησίας το 1881 ευτυχώς διατήρησαν την αρχική στέγη μαζί με τις μαντωσιές του νότιου τοίχου. Οι μαντωσιές αυτές, που έχουν μεταβληθεί σε επιστύλιο, είχαν διακοσμηθεί με μετάλλια με μορφές αγίων όπως και σε πολλές άλλες ξυλόστεγες εκκλησίες.
Τοιχογραφίες σώζονται σήμερα στον ανατολικό τοίχο και την αψίδα και στον βόρειο τοίχο. Στην κορυφή του αετώματος του ανατολικού τοίχου είναι ζωγραφισμένος ο Ευαγγελισμός της Θεοτόκου και πιο κάτω, πάνω όμως από την αψίδα, οι ευαγγελιστές Λουκάς, Ιωάννης, Ματθαίος και Μάρκος. Χαμηλότερα, δεξιά και αριστερά της αψίδας είναι ζωγραφισμένος άγγελος και πιο κάτω, στα βόρεια της αψίδας είναι ζωγραφισμένος ο Πρωτομάρτυρας Στέφανος και στη μικρή αχιβάδα της Πρόθεσης η Άκρα Ταπείνωση. Στα νότια της αψίδας εικονίζεται ο άγιος Νικόλαος.
Στο τεταρτοσφαίριο της αψίδας είναι ζωγραφισμένη η Θεοτόκος όρθια, με τα χέρια υψωμένα σε δέηση, χωρίς τον Χριστό ανάμεσα σε δυο εξαπτέρυγα και τους αρχαγγέλους Μιχαήλ και Γαβριήλ, που υψώνουν το αριστερό χέρι και θυμιούν με το θυμιατήριο που κρατούν στο δεξί χέρι. Πιο χαμηλά, στον ημικυλινδρικό τοίχο της αψίδας είναι ζωγραφισμένοι στα βόρεια του μικρού παραθύρου οι άγιοι Σπυρίδων και Ιωάννης ο Χρυσόστομος, και στα νότια οι άγιοι Βασίλειος και Γρηγόριος ο Θεολόγος.
Ο αρχικός βόρειος τοίχος της εκκλησίας χωρίζεται σε δυο ζώνες. Στην πάνω ζώνη είναι ζωγραφισμένες σκηνές και στην κάτω όρθιοι άγιοι κάτω από τόξα. Στην πάνω ζώνη σώθηκαν η Αποκαθήλωση, με την επιγραφή ὁ Γολγοθᾶς, ο Επιτάφιος Θρήνος, οι Μυροφόρες μπροστά στο Κενό Μνημείο, η εις Άδου Κάθοδος, η Ανάληψη του Χριστού, η Κοίμηση της Θεοτόκου και η Θυσία του Αβραάμ. Στην κάτω ζώνη είναι ζωγραφισμένες οι ακόλουθες τοιχογραφίες: αγία Βαρβάρα, αγία Μαρίνα, άγιος Παντελεήμων, άγιος Ευστάθιος, άγιος Δημήτριος, άγιος Γεώργιος και αρχάγγελος Μιχαήλ. Στη δυτική πλευρά του παραθύρου του βόρειου τοίχου είναι ζωγραφισμένος ο άγιος Μακάριος και στην ανατολική ο άγιος Ζωσιμάς.
Ο ζωγράφος που ζωγράφισε την εκκλησία του Τιμίου Σταυρού στον Παλιόμυλο είναι συντηρητικός. Μένει πιστός στη βυζαντινή παράδοση από την οποία αντλεί την εικονογραφία. Ο συντηρητισμός του φαίνεται όχι μόνο στην απεικόνιση της Ανάστασης με την καθιερωμένη σκηνή της εις Άδου Καθόδου αλλά και με την εικονογράφηση του αγίου Γεωργίου και του αγίου Δημητρίου όρθιων, ενώ κατά τον 16ο αιώνα συνήθως ζωγραφίζονται καβαλάρηδες. Βέβαια δεν είναι μεγάλος ζωγράφος και έχει φανερές αδυναμίες. Όμως ορθή αξιολόγηση του έργου του δεν μπορεί να γίνει προτού καθαριστούν οι τοιχογραφίες που είναι καλυμμένες με καπνιά και σκόνη. Σ' ορισμένες περιπτώσεις τα χρώματα έχουν οξειδωθεί, με αποτέλεσμα να αλλοιωθούν και να γίνουν θαμπά.