Στά χρόνια της Τουρκοκρατίας, κάπου στόν 17ο ἤ 18ο αἰώνα, κτίστηκε ὁ μικρός ναός τῶν Ἁγίων Θεοδώρων. Πρόκειται γιά ἕνα μικρό ἐξωκλήσι, τό ὁποῖο γιά πρώτη φορά μνημονεύεται σέ ἔγγραφα τό 1826.
Τήν ἐποχή ἐκείνη οἱ Ἅγιοι Θεοδωροι ὑπέστησαν καταστροφή. Ἔκτοτε ὁ ναός ἐγκαταλείφθηκε καί παρέμεινε ἐρημωμένος μέχρι τό 1898, ὅποτε τόν ἀνακαίνισε ὁ Παντελής Σπύρου Λέκκας (1846-1913). Μέχρι σήμερα διατηροῦνται οἱ εἰκόνες τοῦ τέμπλου πού ζωγράφισε τότε ὁ μοναχός της μονῆς Πεντέλης Δαμασκηνός Ραυτόπουλος. Στόν Παντελῆ Λέκκα ὀφείλεται κατά μία ἐκδοχή ἡ μετονομασία τοῦ ναοῦ σέ Ἅγιο Ἐλευθέριο, πού ἔγινε καθώς λέγεται μέ ἀφορμή τήν ἥττα τῆς Ἑλλάδας στόν πόλεμο τοῦ 1897 μέ τήν Τουρκία. Ἄλλοι πιστεύουν πώς ἡ μετονομασία ἐπῆλθε ἀργότερα, πρός τιμήν τοῦ Ἐλευθερίου Βενιζέλου.
Στή δεκαετία τοῦ 1930 ἄρχισαν νά ἐγκαθίστανται στήν περιοχή τοῦ Ἁγίου Ἐλευθερίου οἱ πρῶτοι μόνιμοι κάτοικοι. Μετά τόν πόλεμο, ὁ πληθυσμός ἄρχισε νά αὐξάνεται ραγδαία. Ἰδίως μέ τόν ἐρχομό πολλῶν νησιωτῶν, καί σύντομα δημιουργήθηκε στήν περιοχή μία κανονική συνοικία. Ἦταν τό 1963 ὅταν μία ὁμάδα κατοίκων τῆς περιοχῆς (ὁ Γεώργιος Ζαμαρίας, ὁ Ζαννής Καλογήρου ἤ Στάμενας καί ἡ γυναίκα τοῦ Χαρίκλεια-Φλώρα Ζαμαρία, ὁ Ἀθανάσιος Ρήγας, ὁ πάπα-Κώστας Λάσκαρης, ὁ Παπαδημητρίου καί ὁ βασιλικός ἐπίτροπος Θεοδόσιος Σπεράντζας) πέτυχαν νά ἱδρυθεῖ ἀνεξάρτητη ἐνορία μέ κέντρο τό ναό τοῦ Ἁγίου Ἐλευθερίου.
Τό ἴδιο ἔτος ἦρθε ὁ πρῶτος ἐφημέριος του ναοῦ, π. Ἰωάννης Κοντός. Τόν ἑπόμενο χρόνο ἀγοράστηκε ἀπό τήν ἐνορία τό κτῆμα ἰδιοκτησίας Ζαχαρία Καπριλιᾶν, πρώην Σταύρου Καλοζύμη, πού βρισκόταν μπροστά ἀπό τό ἐκκλησάκι. Ὁ μικρός ναός δέν ἐπαρκοῦσε βέβαια γιά νά στεγάσει τίς ἀνάγκες τῆς ὁλοένα αὐξανόμενης πληθυσμιακά ἐνορίας. Τό 1979 θεμελιώθηκε ὁ νέος μεγάλος ναός, στό οἰκόπεδο πού εἶχε ἀγοραστεῖ μπροστά ἀπό τόν παλαιό.
