Είναι ο πρώτος ναός που ιδρύθηκε στον συνοικισμό της Νέας Κοκκινιάς, από τους πρώτους πρόσφυγες του 1922. Λειτουργούσε σε αντίσκηνο που έδωσε στους πρόσφυγες ο Ν. Πλαστήρας και στήθηκε στην ανατολική πλευρά της πλατείας Αγ. Νικολάου. Το 1923 πραγματοποιήθηκε η θεμελίωση του ναού από τον Αρχιερατικό Επίτροπο Ν. Κοκκινιάς Σεβαστείας Γερβάσιο. Ο ναός ολοκληρώθηκε 1928 – 1929 με τις συνδρομές των κατοίκων και εγκαινιάστηκε από τον Μητροπολίτη Σεβαστείας Γερβάσιο το 1930. Το τέμπλο του ναού είναι ξυλόγλυπτο από ξύλο καρυδιάς, λαϊκής τεχνοτροπίας και αναπαριστώνται χριστιανικά σύμβολα, όπως πουλιά, άμπελος και το θέμα των Κάιν και Άβελ (που αποτελεί σημαντική λεπτομέρεια), κ.ά. Ξυλόγλυπτος είναι και ο σημερινός Επιτάφιος του ναού, που φιλοτεχνήθηκε από τον ξυλογλύπτη Γεώργιο Γρηγορίου (δωρεά οικ. Τερκεσίδου) και είναι αντίγραφο του εκ. Μ. Ασίας Επιταφίου του Αγ. Ιωάννου Χρυσοστόμου Νικαίας.
Το Τέμπλο του ναού μεταφέρθηκε κομμάτι – κομμάτι από τον ιερό ναό του Αγίου Στεφάνου της Νίγδης στην Καππαδοκία με τη βοήθεια του Γερβάσιου κατά την ανταλλαγή το 1923, όπως και ο άμβωνας, το δεσποτικό και δύο προσκυνητάρια. Το 1947 καθιερώθηκε επίσημα από την Ιερά Σύνοδο η εορτή της πόλης την ημέρα της εορτής των 318 Θεοφόρων Πατέρων της Α΄ εν Νικαία Οικουμενικής Συνόδου. Ο ναός αγιογραφήθηκε αργότερα από τους αδελφούς Σούτσους με την επίβλεψη του ακαδημαϊκού Βυζαντινολόγου Αναστασίου Ορλάνδου.
Ο ναός είναι τρισυπόστατος και τιμάται στη μνήμη του Αγ. Νικολάου, των Αγίων 318 Θεοφόρων Πατέρων των συγκροτησάντων την Α΄ εν Νικαία Οικουμενική Σύνοδο και της Κοιμήσεως της Θεοτόκου. Πρώτος ιερέας ήταν ο Βασίλειος Παπαδόπουλος που πρωτοστάτησε στην ανέγερση του ναού. Στον περίβολο του ναού ενταφιάστηκε ο πρώτος Μητροπολίτης της Νίκαιας Γεώργιος Παυλίδης (Ιερά Μητρόπολις Νικαίας, Νίκαια, Θεολογία, Πολιτισμός 325 – 1987, Νίκαια 1988, σ. 356 – 357, Αρχοντία Παπαδοπούλου, Η Αττική Νίκαια. Ιστορική μελέτη, Δ΄ έκδοση εμπλουτισμένη, Λεξίτυπον, Αθήνα 2023, σ. 182 - 188).