Στο Νοτιοδυτικό άκρο του οικισμού των Ματάλων εκεί που ο κάθετος βράχος σταματά την οικοδόμηση, κτισμάτων βρίσκεται ο σπηλαιώδης ναός της παναγίας που είναι αφιερωμένος στην Κοίμηση της Θεοτόκου. Η σπηλιά που αρχικά φαίνεται ότι ήταν φυσική άρχισε να λαξεύεται για να φτάσει στην κατάσταση που βρίσκεται σήμερα. Επειδή η περιοχή των Ματάλων είναι γεμάτη με λαξευμένες σπηλιές από την αρχαιότητα πιστεύεται ότι και η σπηλιά της Παναγίας είχε λαξευτεί την ίδια εποχή. Ο Στ. Ξανθουδίδης γράφει ότι το σπήλαιο αυτό ήταν κατά την αρχαιότητα οικογενειακός τάφος (Χριστιαν. Επιγραφή σελ. 134). Με την διάδοση του Χριστιανισμού όπως και τόσα άλλα σπήλαια Θα έγινε τόπος λατρείας από τα πρώτα χριστιανικά χρόνια. Για Πρώτη φορά αναφέρεται ο ναός στην ενετική περίοδο, σε ένα ανέκδοτο Βενετσιάνικο έγγραφο όπου λεει ότι εδώ υπήρχε ο ναός της Παναγίας και ότι στην είσοδό του υπήρχε μια ελληνική επιγραφή που έλεγε:

Την περίοδο αυτή (την Βενετσιάνικη) ο οικισμός λεγόταν Santa Maria di Matala Madonna di Matala που σημαίνει ότι ο οικισμός των Ματάλων συνδεόταν άμεσα με το όνομα της Παναγίας της οποίας το όνομα έφερε σαν πρώτο συνθετικό της ονομασίας του την εποχή εκείνη. Στο ιερό του σπηλαιώδους ναού υπάρχουν δύο κυανόκρανα που χρησιμοποιήθηκαν το ένα σαν αγία Τράπεζα και το άλλο σαν αγία πρόθεση ίσως από την A’ Βυζαντινή Περίοδο. Ο σπηλαιώδης ναός της Κοιμήσεως της Θεοτόκου στα Μάταλα ανήκει στην ιερά μονή της Οδηγήτριας. Το Μοναστήρι είχε ακόμη στα Μάταλα κατά το 1870-72 κτηματική περιουσία εκτάσεως 112 μουζουρίων τα οποία πήρε μετέπειτα το κράτος και τα μοίρασε στους εφέδρους πολεμιστές (εφεδρικά).