Η εκκλησία του Αγίου Θεοδοσίου στην Αχέλεια της επαρχίας Πάφου, είναι σταυρόσχημη με τρούλλο. Τα σκέλη του σταυρού διαγράφονται ελεύθερα. Είναι κτισμένη με μισοκατεργασμένους και ακατέργαστους πωρόλιθους. Το ανατολικό σκέλος είχε ερειπωθεί και αναστηλώθηκε πριν από λίγα χρόνια. Το μέγιστο μήκος της εκκλησίας χωρίς την αψίδα είναι 10,53 μ. και το μέγιστο πλάτος 8,61 μ. Το πλάτος και το μήκος των σκελών διαφέρει ευρύτερα, και επιμηκέστερα είναι το δυτικό και το ανατολικό σκέλος. Σήμερα υπάρχει μια μόνο είσοδος στο μέσο του νότιου τοίχου του νότιου σκέλους. Άλλη θύρα, ευρύτερη, υπήρχε στο μέσο του δυτικού τοίχου του δυτικού σκέλους αλλά εντοιχίσθηκε σε παλαιότερα χρόνια. Στην εκκλησία σώζονται υπολείμματα τριών στρωμάτων τοιχογραφιών. Το παλαιότερο στρώμα έχει σχεδόν καταστραφεί τελείως όπως και το νεότερο στρώμα. Από το νεότερο στρώμα, ίσως του 16ου αιώνα, σώζονται στον βόρειο τοίχο του δυτικού σκέλους της εκκλησίας μισοκατεστραμμένες οι τοιχογραφίες της αγίας Αναστασίας της Φαρμακολύτριας και των αγίων Ανδρονίκου και Αθανασίας.
Σε καλύτερη κατάσταση σώζονται τοιχογραφίες του δευτέρου στρώματος. Τέτοιες είναι οι τοιχογραφίες των αποστόλων Πέτρου και Παύλου κάτω από τόξα στο νότιο τοίχο του δυτικού σκέλους. Οι τοιχογραφίες αυτές είναι αναθηματικές και συνοδεύονται από τα πορτραίτα ενός νέου που πέθανε και στη μνήμη του οποίου έγινε η τοιχογραφία και ενός άντρα που πιθανότατα είναι ο δωρητής. Άλλες τοιχογραφίες του ιδίου στρώματος είναι οι τοιχογραφίες του αγίου Νικολάου και του αγίου Θεοδοσίου στον ανατολικό τοίχο του βόρειου σκέλους και οι μισοκατεστραμμένες τοιχογραφίες ενός διακόνου και ενός έφιππου στρατιωτικού αγίου στο δυτικό τοίχο του ιδίου σκέλους του ναού. Στο βόρειο τοίχο του βόρειου σκέλους εικονίζεται σε υπερφυσικό μέγεθος, σε στάση μετωπική, στρατιωτικός άγιος πολύ κατεστραμμένος. Υπολείμματα τοιχογραφιών υπάρχουν και στην καμάρα του βόρειου σκέλους και στον τρούλλο, που δεν βοηθούν στη χρονολόγηση. Μόνο οι τοιχογραφίες του δεύτερου στρώματος μπορούν να χρονολογηθούν στο 13ο αιώνα. Αναμφίβολα είναι, από την άποψη τέχνης, από τις πιο σημαντικές τοιχογραφίες του 13ου αιώνα στην Κύπρο και αποτελούν φυσιολογική εξέλιξη της τέχνης του τέλους του 12ου αιώνα. Οι τοιχογραφίες αυτές όμως έχουν αποβάλει την υπέρμετρη ραδινότητα και ταυτόχρονα έχουν αποκτήσει κάποιο όγκο και βάρος.