Κατά την παράδοση η εικόνα της Παναγίας επέπλεε επάνω στα κύματα της θάλασσας.

Το ρεύμα της θάλασσας ήτανε τέτοιο που προφανώς η εικόνα ερχότανε από τα παράλια της Μικράς Ασίας, από όπου την πέταξαν στην θάλασσα κάποιοι πιστοί χριστιανοί για να την διασώσουν από τα βέβηλα χέρια και τις καταστροφικές συνέπειες του μίσους των Τούρκων.

Την εικόνα τελικά βρήκε ένας σφουγγαράς πιασμένη στα δίχτυα του, ο οποίος και την παρέδωσε στον καπετάνιο του νησιού Καραντώνη.

Ο ευσεβής αυτός καπετάνιος την πήρε στο καράβι του, και όταν έπιασε ξηρά την τύλιξε με μυρτιές και την πήγε σπίτι του, το βράδυ όμως η Παναγία φανερώθηκε στον ύπνο του και του υπέδειξε το κτήμα του σαν τον τόπο όπου θα επιθυμούσε να έκτιζαν τον ναό Της.

Η γυναίκα του καπετάνιου τοποθέτησε την εικόνα στο εικονοστάσι και πέταξε τις ξεραμένες μυρτιές στο κτήμα.

Την άλλη μέρα ενώ άρχιζαν τις ετοιμασίες για να κτίσουν τον ναό με μεγάλη τους έκπληξη είδανε τις ξεραμένες μυρτιές, που είχε πετάξει στο κτήμα η καπετάνισσα, να “πιάνουν”.

Οι μυρτιές αυτές τελικά έγιναν μεγάλα δέντρα που υπάρχουν ως και σήμερα και από αυτά πήρε και το όνομά της η περιοχή.

Κατά μια άλλη εκδοχή, γύρω στα 1880 ο Καλύμνιος έμπορος Καραντώνης, ενώ πήγαινε σφουγγάρια στην Τουρκία και εμπορευόταν τρόφιμα και άλλα υλικά αγαθά, ένας Τούρκος έμπορος επειδή ήξερε πως αυτός ήταν χριστιανός, του έδωσε την εικόνα της Παναγίας, έτσι ώστε να μην την κάψουν οι άλλοι Τούρκοι.

Ο Καλύμνιος έμπορος έκρυψε την εικόνα μέσα σε ένα τσουβάλι με μυρτιές στο αμπάρι του καϊκιού του, από φόβο μήπως του την κλέψουν και την μετέφερε τελικά στην Κάλυμνο.

Η εκκλησία σήμερα είναι ιδιοκτησία της οικογένειας Βουβάλη.

Πηγή: Greek Orthodox Religious Tourism, Αβέρωφ