Ο Όσιος Θεόδουλος ήταν υιός του σοφού Νείλου, ο οποίος έγινε έπαρχος Κωνσταντινουπόλεως, αλλά άφησε την δόξα του κόσμου και έγινε μοναχός στο όρος Σινά μαζί με τον υιό του. Οι όσιοι έζησαν προ των μέσων του 5ου αιώνος μ.Χ. επί βασιλείας Θεοδοσίου Β (408-450 μ.Χ.).Εκεί λοιπόν που διέμεναν, ο Νείλος, ο υιός του Θεόδουλος και οι άλλοι μοναχοί, ξαφνικά τους επιτέθηκαν βάρβαροι και άρχισαν να τους κατασφάζουν. Ο Νείλος κατόρθωσε να διαφύγει. Τον υιό του όμως, Θεόδουλο τον πήραν μαζί τους αιχμάλωτο. Στην αρχή θέλησαν να τον φονεύσουν, αλλά κατόπιν τον πούλησαν και τον αγόρασε ο Επίσκοπος της Λούζης, ο οποίος και του απέδωσε την ελευθερία του.
Αργότερα, ο Όσιος Θεόδουλος συναντήθηκε με τον πατέρα του, τον Όσιο Νείλο, ο οποίος είχε διαφύγει από την σφαγή των Αββάδων του Σινά και μετέβη μαζί του σε ερημικό τόπο για άσκηση και προσευχή. Κατά την εκεί παραμονή τους συνέγραψαν λόγους και επιστολές με πολύτιμες πνευματικές συμβουλές περί του τρόπου κατά τον οποίο οφείλουν να ζουν οι μοναχοί, για να επιτύχουν την ένωσή τους με τον Θεό.
Ο Όσιος Θεόδουλος, κοιμήθηκε με ειρήνη. Τα ιερά λείψανά του μετεκομίσθησαν στην Κωνσταντινούπολη, επί αυτοκράτορα Ιουστίνου, όπου και τα κατέθεσαν στο Ναό των Αγίων Αποστόλων.
Η Σύναξη του Οσίου Θεοδούλου καθώς και άλλων Αγίων Ασκητών ετελείτο στην Κωνσταντινούπολη, στο Ναό των Αποστόλων Πέτρου και Παύλου που βρίσκεται στο ορφανοτροφείο.
