Μετά την σύσταση του συνοικισμού της Νέας Αλικαρνασσού και την ανέγερση των πρώτων οικιών (1924 - 1925) έγινε προφανής και η ανάγκη δημιουργίας δημοτικού σχολείου για την κάλυψη των πνευματικών αναγκών των νεαρών προσφύγων.
Η ανάγκη αυτή καλύφθηκε με την ένταξη των μικρών μαθητών στο μονοτάξιο δημοτικό σχολείο που λειτουργούσε ήδη από το 1917 (Φ.Ε.Κ. 279/24-11-1917) στη περιοχή, όπου συστήθηκε ο συνοικισμός, σε ένα οίκημα - αίθουσα που είχε παραχωρηθεί προσωρινά από την Επιτροπή
Αποκατάστασης Προσφύγων (Ε.Α.Π.) και που σήμερα είναι η οικία του κ. Απόστολου Πουλιού.
Κατά το έτος 1927 οι μαθητές του δημοτικού σχολείου μεταφέρονται σε νεόδμητο κτήριο που έχει ανεγερθεί ειδικά για τη στέγαση τους σε ένα οικόπεδο περίπου 5.000 τ.μ., το οποίο παραχωρήθηκε από την Επιτροπή Αποκατάστασης Προσφύγων αποκλειστικά για την σχολική εφορία της κοινότητας της Νέας Αλικαρνασσού. Το σχολείο, που έχει πλέον προαχθεί σε 3τάξιο ονομάστηκε «Ηροδότειος Δημοτική Σχολή Κοινότητος Νέας Αλικαρνασσού» προς τιμή του πρώτου ιστορικού «Ηροδότου» ο οποίος καταγόταν από την Αλικαρνασσό της Μικράς Ασίας.
Το έτος 1929 ο συνεχής αυξανόμενος αριθμός των μαθητών έχει ως αποτέλεσμα την προαγωγή του σχολείου σε 5τάξιο (Υ.Π. 147/18-4-1929), ενώ συνάμα ολοκληρώνεται η αποπεράτωση των πέντε αιθουσών διδασκαλίας και των δύο γραφείων. Το 1952 το σχολείο προάγεται σε 6τάξιο (Υ.Π. 250/6- 9-1952) λόγω του κατ' έτους αυξανόμενου αριθμού των μαθητών.
Σημαντικό ρόλο στην οργάνωση, διοίκηση και διεκπεραίωση των εκπαιδευτικών ζητημάτων έπαιξε η κυρία Άννα Ιατράκη, η πρώτη δασκάλα που διορίσθηκε στο σχολείο της Νέας Αλικαρνασσού, η οποία άσκησε και το ρόλο της διευθύντριας από το 1926 έως το 1958. Η αρμονικής της συνεργασία με τους συναδέλφους της, σε συνδυασμό με τις παιδαγωγικές της ικανότητες και τον προοδευτικό της χαρακτήρα, οδήγησαν στην σταδιακή προαγωγή του σχολείου, ενώ η ίδια αποτέλεσε πνευματική μητέρα εκατοντάδων παιδιών.
