Η παράδοση θέλει τον ναό να χτίστηκε με γάλα.
Σύμφωνα λοιπόν με την παράδοση, επί Τουρκοκρατίας, οι Τούρκοι κατακτητές είχαν γκρεμίσει και λεηλατήσει το εκκλησάκι του Τιμίου Σταυρού στο Στρούμπουλα, όπως τις περισσότερες εκκλησίες του τόπου μας.
Μετά από πίεση των κατοίκων της Τυλίσου και των γύρω περιοχών, όπως Μάραθος και Δαμάστα, οι Τούρκοι διοικητές πιεζόμενοι από το θρησκευτικό αίσθημα των κατοίκων και φοβούμενοι για εξέγερση, τούς άφησαν να το ξαναχτίσουν αλλά υπό ένα όρο: έπρεπε να το τελειώσουν μέσα σε μια εβδομάδα, ούτε ώρα παραπάνω. Αν προλάβαιναν, καλώς. Αν όχι, πράγμα για το οποίο ήταν σίγουροι οι Τούρκοι, θα τούς το γκρέμιζαν επί τόπου.
Όλοι οι χωριανοί έπιασαν δουλειά με ζήλο. Δούλευαν μέρα-νύχτα για να προλάβουν το χτίσιμο. Οι συνθήκες ήταν πολύ αντίξοες. Οι διαδρομές για να μεταφέρουν τα υλικά, πολύ μακρινές. Τα κουβαλούσαν με τα γαϊδουράκια τους μέρα-νύχτα για να προλάβουν. Την τελευταία στιγμή τους λείπεται το νερό και το πηγάδι στο βουνό είχε στερέψει. Ήταν αδύνατο να προλάβουν μέσα στη νύχτα να κατέβουν το βουνό για να φέρουν νερό να τελειώσουν το χτίσιμο της σκεπής που τούς είχε μείνει ακόμα.
Τότε μαζεύονται οι βοσκοί από τη γύρω περιοχή, αρμέγουν τα πρόβατά τους και τούς δίνουν το γάλα που είχαν μαζέψει. Μ’ αυτό το γάλα μάλαξαν τη λάσπη οι χωριανοί και τελείωσαν το χτίσιμο της σκεπής στην ώρα τους. Οι Τούρκοι τα έχασαν, δεν πίστευαν στα μάτια τους αλλά τήρησαν τη συμφωνία τους και τούς άφησαν να λειτουργήσουν.
Από τότε το εκκλησάκι του Τιμίου Σταυρού είναι στη θέση του στην κορυφή του Στρούμπουλα και χιλιάδες πιστοί το επισκέπτονται κάθε χρόνο στις 13 και 14 του Σεπτέμβρη… Επίσης του Προφήτη Ηλία 19 και 20 Ιουλίου …