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

Το σωζόμενο τμήμα του ναού είχε αρχικά καμαρωτή οροφή, όπως μαρτυρούν οι γενέσεις ενισχυτικών τόξων στους πλάγιους τοίχους. Η αρχική τοιχοδομία του μνημείου είναι χαρακτηριστική για την εποχή οικοδόμησής του (11ος / 12ος αι.) : πλινθοπερίκλειστο σύστημα δόμησης, με παρεμβολή λίθινων σταυρών και οδοντωτές ταινίες στα παράθυρα. Στο δυτικό τοίχο, που έχει υποστεί ανακατασκευή, έχουν ενσωματωθεί μέλη μεσοβυζαντινού τέμπλου.

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