Η μετονομασία της πόλης, οι μετονομασίες των οδών της

Με την ίδια απόφαση του υπουργού εσωτερικών Ι. Ράλλη αναγνωρίζονταν οι περισσότεροι προσφυγικοί συνοικισμοί της Αττικής σε ανεξάρτητους δήμους ή κοινότητες.  Έξι χρόνια αργότερα το Δημοτικό Συμβούλιο προκήρυξε διαγωνισμό για την μετονομασία του Δήμου, ζητώντας προτάσεις που να προέρχονται από ιστορικές πόλεις της Μικράς Ασίας, του Πόντου και της Θράκης. Ο νικητής θα λάμβανε και χρηματικό έπαθλο 2.000 δραχμών. Τα τοπωνύμια Μίλητος, Ίλιον, Τροία, Έφεσος, Πάφρα, Τρωάς και Νίκαια ήταν ανάμεσα στις δεκάδες προτάσεις που κατατέθηκαν. Προκρίθηκε το όνομα Νίκαια, που αποτελούσε πρόταση του δικηγόρου Ιωάννη Μελά, μετέπειτα δημάρχου του Δήμου, ως το πιο συμβολικό και το πιο ιστορικό για τον προσφυγικό δήμο. Στις 3 Σεπτεμβρίου του 1940 δημοσιεύτηκε το ΦΕΚ που ενέκρινε την μετονομασία. 

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