Το μοναδικής ομορφιάς και ιστορίας μοναστήρι με οχύρωση είναι κτισμένο στο βουνό Κουκούλα βόρεια από τον Βαθύ Καλύμνου.
Βρίσκεται μπροστά σε μια σπηλιά στο εσωτερικό της οποίας υπάρχει εκκλησάκι και πηγάδι.
Πιστεύεται ότι στη θέση αυτή υπήρχε Βυζαντινό κάστρο, σύμφωνα με τους Spiteri (1994) και Παραδείση (1976). Επίσης, σύμφωνα με τον Καλύμνιο αρχαιολόγο Μιχαήλ Κουτελλά (2006), το μοναστήρι χτίστηκε τον 18ο αιώνα πάνω στο παλιό κάστρο.
Κάτω από τους ασβεστωμένο (και μεταγενέστερο) τείχος του μοναστηριού με τις στρογγυλεμένες «τουρκικού τύπου» πολεμίστρες διακρίνονται οι παλιότερες πολεμίστρες τύπου χελιδονουράς. Πάνω από τη μικρή πύλη του μοναστηριού υπάρχει ένα ακόμη οχυρωματικό στοιχείο: η βάση μιας καταχύστρας.
Σε ένα σπήλαιο στο βουνό στα βόρεια από το Βαθύ, ξεχωρίζει το εγκαταλελειμμένο πλέον μοναστήρι της Παναγίας Κυρά Ψηλής. Σύμφωνα με τον επικρατέστερο λαϊκό θρύλο, το μοναστήρι κτίστηκε από έναν Καλύμνιο που είχε μεταναστεύσει και αλλαξοπιστήσει, ο οποίος όμως όταν επέστρεψε στο νησί θυμήθηκε τις ρίζες του και πίστεψε ξανά στο Θεό. Ένας άλλος θρύλος αναφέρει πως κάποιος βοσκός, ψάχνοντας ένα τράγο του που είχε εξαφανιστεί, ανακάλυψε τη σπηλιά και στο εσωτερικό της μια εικόνα της Παναγίας. Ο βοσκός προσπάθησε πολλές φορές να μεταφέρει την εικόνα στο χωριό, αλλά στα μισά της διαδρομής η εικόνα επέστρεφε μόνη της στη σπηλιά.
Οι ντόπιοι διαμόρφωσαν το σπήλαιο σε εκκλησία και μετέφεραν με λιτανείες την εικόνα στο Βαθύ. Κάθε χρόνο τον Δεκαπενταυγούστο την επαναφέρουν στο εκκλησάκι όπου γίνεται ολονύκτια γιορτή. Ανήμερα το Δεκαπενταύγουστο, γίνεται μεγάλο παραδοσιακό πανηγύρι στο Βαθύ, στην εκκλησία της Παναγίας της Κυρά Ψηλής.