Στην τοποθεσία της Παχιάς Άμμου βρίσκεται η εκκλησία της Παναγίας της Κρημνιώτισσας, που πήρε την ονομασία της από τον κρημνό, τον ψηλό βράχο πάνω στον οποίο είναι χτισμένη. Ο ναός εντυπωσιάζει τόσο λόγω του σημείου στο οποίο βρίσκεται, αφού μοιάζει να αιωρείται και προσφέρει μαγευτική θέα του Βορείου Αιγαίου, όσο και λόγω της ιστορίας που υφάνθηκε γύρω από αυτόν. Σύμφωνα λοιπόν με την παράδοση, η εικόνα που φυλάσσεται εδώ είχε ριχτεί στη θάλασσα από χριστιανούς κατοίκους της Μικράς Ασίας, για να σωθεί από τις λεηλασίες των εικονομάχων. Ήταν γύρω στο 1700, όταν ένα καράβι, πλέοντας στα νερά γύρω από τη Σαμοθράκη, κινδύνεψε να βυθιστεί εξαιτίας της σφοδρής θαλασσοταραχής. Τότε ο καπετάνιος διέκρινε στα νερά την εικόνα και έδωσε εντολή να την ανεβάσουν στο πλοίο. Αμέσως η φουρτούνα κόπασε. Το ίδιο βράδυ, η Παναγία εμφανίστηκε στον καπετάνιο στον ύπνο του και του ζήτησε να την πάει στη Σαμοθράκη, όπως και έγινε. Ο ιερέας του νησιού τοποθέτησε την εικόνα στην εκκλησία, όμως κάθε βράδυ η εικόνα έφευγε και οι κάτοικοι την έβρισκαν στον ψηλό βράχο. Δεν άργησαν να καταλάβουν την επιθυμία της κι έτσι έχτισαν το παρεκκλήσι που κοσμεί σήμερα τον κρημνό.