(από το Θεός + δούλος) = ο αφωσιωμένος στον Θεό.
Eπαρχίαν γης Oυρανών επαρχίας,O Θεόδουλος αντέδωκεν εμφρόνως.
Υπήρξε πατρίκιος στα χρόνια του Θεοδοσίου του Μεγάλου (379-395) και ήταν άνδρας διάσημος για τη σύνεση, την αρετή και τη σεμνότητα της ζωής του. Έτσι προήχθηκε στο αξίωμα του Έπαρχου από τον βασιλιά Θεοδόσιο. Βλέποντας όμως τις αδικίες των ισχυρών, αηδίασε και αφού παραιτήθηκε του αξιώματος του, ιδιώτευε. Μετά δύο χρόνια από τον γάμο του, πέθανε η σύζυγός του και αυτός πήγε στην Έδεσσα, αφού μοίρασε τη μεγάλη του περιουσία στους φτωχούς και ευαγή ιδρύματα. Εκεί και ενώ ήταν στο 42ο έτος της ηλικίας του, ανέβηκε πάνω σ' ένα στύλο και με τις πιο αντίξοες συνθήκες έκανε σκληρή άσκηση. Έτσι, με άσκηση και προσευχή, αφού έζησε για άλλα 40 χρόνια πάνω στο στύλο, απεβίωσε ειρηνικά.