Το σπήλαιο των αγίων Θεοδώρων είναι διαμορφωμένο σε ναΐδριο με την προσθήκη χτιστού τέμπλου και με την τοιχογράφηση των επιφανειών του βράχου, θυμίζοντας τις σπηλαιώδεις εκκλησίες της Καππαδοκίας. Oι τοίχοι και το εικονοστάσιο είναι πλούσια διακοσμημένοι με βυζαντινές τοιχογραφίες δύο φάσεων: Η πρώτη χρονολογείται στα τέλη του 11ου αι. και ανήκει στη λεγόμενη μοναστική τεχνοτροπία, η δεύτερη στη στροφή του 12ου με τον 13ο αι. και διακρίνεται από τα χαρακτηριστικά της λεγόμενης μεταβατικής εποχής. Η τέχνη τους αντανακλά τη μεγάλη παράδοση αγιογραφιών της Κωνσταντινούπολης.
Ζωγραφική διακόσμηση καλύπτει τα πλάγια τοιχώματα του διαδρόμου εισόδου και του ναΐσκου, όλη την επιφάνεια του κτιστού τέμπλου και τα τοιχώματα του ιερού βήματος. Είναι πολύ πιθανό ότι αρχικά στο σπήλαιο υπήρξαν μεμονωμένες ζωγραφικές παραστάσεις με χρονική ίσως απόσταση μεταξύ τους και στη συνέχεια έγινε ένα ενιαίο τοιχογραφικό σύνολο που κάλυψε και τις παλαιότερες τοιχογραφίες, όπου υπήρχαν.Η θεματική κυριαρχία των απεικονίσεων της Θεοτόκου και στο αρχικό και στο νεώτερο στρώμα, ενισχύει την άποψη ότι το παρεκκλήσιο ήταν αφιερωμένο αρχικά στην Παναγιά. Oι τοιχογραφίες διακρίνονται για την εξαιρετική τεχνοτροπία τους, σπάνια δείγματα μνημειακής ζωγραφικής της περιόδου αυτής.
Οι δοξασίες των κατοίκων για τους Αγίους Αποστόλους πολλές, όπως η παράδοση τους θέλει να αγιοποιούνται γιατί απάλλαξαν την περιοχή από σκληρούς ληστές που βασάνιζαν τους κατοίκους και ήταν ο τρόμος και ο φόβος. Μια φορά τον χρόνο ο ναός ζωντανεύει από δεκάδες προσκυνητές που ανεβαίνουν τα χωμάτινα σκαλιά και ανάβουν κεριά στον ναό των σπηλαίων όπου υπάρχουν εντυπωσιακές τοιχογραφίες. Αυτό το σημείο θα πρέπει να προσεχθεί ώστε και η πρόσβαση να είναι πιο εύκολη και ασφαλής, ενώ και η εκκλησία να αναλάβει την προβολή του ως σημείο θρησκευτικού τουρισμού που ελάχιστοι πλην των ντόπιων γνωρίζουν.