Είναι τόσες οι παλιές και ιστορικές εκκλησίες του Δήμου Βιάννου, που καταλαβαίνει κανείς πως άλλοι τόσοι και περισσότεροι, θα είναι οι θρύλοι που τις συνοδεύουν.
Μια από αυτές, είναι η εκκλησία της Παναγίας της γαλατοκτισμένης ή νηστικοκτισμένης, που βρίσκεται στην Κάτω Σύμη.
Σύμφωνα με δημοσίευμα του Εμμανουήλ Χαλκιαδάκη στα "Βιαννίτικα Νέα" (φ.4 Ιούνιος 1976), κάποτε ο άρχοντας της Σύμης φιλοξένησε μια αρχόντισσα από το Ηράκλειο, η οποία είχε ξεκινήσει να πάει ένα τάμα σε μια εκκλησία στο Λασίθι. Ο οικοδεσπότης άρχοντας όμως φέρθηκε απρεπώς στην πανέμορφη Αρχόντισσα κι εκείνη επέστρεψε στο Ηράκλειο πικραμένη χωρίς να φτάσει στον προορισμό της, διηγούμενη στον άνδρα της, ότι της συνέβη.
Ο άρχοντας από το Ηράκλειο δεν έμεινε άπραγος και ενημέρωσε τους άρχοντες της περιοχής για το περιστατικό, οι οποίοι αποφάσισαν πως η τιμωρία που άξιζε σ'αυτον της Σύμης, θα ήταν είτε να τον αλείψουν με μέλι γυμνό και να τον φάνε οι σφήκες ή να τον χτίσουνε ζωνταντό σε έναν τοίχο της Λότζια στον Χάνδακα. Ο άρχοντας πέθανε βασανιστικά με έναν από τους δύο τρόπους και η γυναίκα του προκειμένου να συγχωρεθεί ο άνδρας της, αποφάσισε να χτίσει μια εκκλησία όπου αντί για νερό, η λάσπη θα φτιαχνόταν από το γάλα των αμέτρητων προβάτων της και οι εργάτες θα δούλευαν νηστικοί μέχρι να την ολοκληρώσουν. Έτσι, χτίστηκε η Παναγία η Γαλακτοκτισμένη ή Νηστικοκτισμένη, με πιθανή ημερομηνία ανέγερσης το 1351.
Αξίζει να προσθέσουμε, ότι εκεί θάφτηκε κι ένας από τους σημαντικότερους οπλαρχηγούς της Ανατολικής Κρήτης επί Τουρκοκρατίας, ο Συμιανός καπετάν Χατζηαναγνώστης.
