Είχαν περάσει δέκα χρόνια από το 1922 και τον μεγάλο ξεριζωμό, όταν το 1932 Μικρασιάτες πρόσφυγες από την Αλικαρνασσό, (Βodrum, όπως τη λένε οι Τούρκοι, αλλά και Πετρούμι στα ελληνικά εκείνων των χρόνων) που είχαν πια εγκατασταθεί στο Ηράκλειο της Κρήτης και είχαν ιδρύσει από το 1925 τη Νέα Αλικαρνασσό, αποφάσισαν να ιδρύσουν τον Ποδοσφαιρικό Αθλητικό Σύλλογο Αλικαρνασσού (Π.Α.Σ.Α.) «ΗΡΟΔΟΤΟΣ». Η απόφαση του Πρωτοδικείου Ηρακλείου βγήκε το Νοέμβριο του 1932. Η επιλογή του ονόματος δεν ήταν τυχαία, αλλά έγινε για να τιμήσει τον Ηρόδοτο τον πρώτο ιστορικό που καταγόταν από την Αλικαρνασσό και για να θυμίζει τη χαμένη πατρίδα. Η προτομή του ιστορικού είναι και το έμβλημα της ομάδας, που έχει χρώματα μπλε και άσπρο.
Τον Νοέμβριο του 1931 αναφέρεται η πρώτη συνάντηση της Αθλητικής Ένωσης Νέας Αλικαρνασσού Ηρόδοτος σε φιλική συνάντηση με τον Ηρακλή, πριν από την προσωρινή διακοπή της λειτουργίας του. Το επόμενο έτος ο σύλλογος επανιδρύεται με πρωτοβουλίες του γιατρού Μιχαήλ Βελισσάριου για να αδρανήσει στα επόμενα χρόνια.
Απολύτως συνεκτικές οι προσφυγικές κοινότητες εκείνων των χρόνων είχαν ταυτόχρονη δραστηριότητα σε πολλούς τομείς κυρίως με την ίδρυση συλλόγων, προσπάθειες για ίδρυση σχολείων και εκκλησιών (στη Νέα Αλικαρνασσό τον Άγιο Νικόλαο), αλλά και αθλητικών ομάδων.
Η Νέα Αλικαρνασσός, παραθαλάσσια όντας, θύμιζε έντονα στους πρόσφυγες το Πετρούμι – Bodrum – Aλικαρνασσό της Μικράς Ασίας, ενώ στις μεταξύ τους συζητήσεις οι πρόσφυγες αποκαλούνται όχι πάντα Αλικαρνασσιώτες, αλλά Πετρουμιανοί.
Ο αθλητισμός εκτός από παράγοντας εσωτερικής συσπείρωσης των μελών της προσφυγικής κοινότητας, αποτέλεσε και εργαλείο για την κοινωνικοποίησή της και την αποδοχή της από τα στρώματα των «γηγενών» που σε αρκετές περιπτώσεις δεν είχαν αντιμετωπίσει με θετικό τρόπο τους νεοφερμένους συμπολίτες τους. Η διαδικασία αυτή δεν είναι χαρακτηριστικό του Ηρακλείου, αλλά φαινόμενο που παρουσιάστηκε σε όλα σχεδόν τα μέρη όπου έγιναν ανάλογες εγκαταστάσεις προσφύγων.
Η προσπάθεια αυτή αν και σε γενικές γραμμές έφερε αποτελέσματα, δεν απέφυγε και τις γνωστές ακόμα και στις μέρες μας ποδοσφαιρικές αντιπαλότητες, καθώς το «πάμε να παίξουμε με τους Τούρκους», ή τους «τουρκόσπορους», ή τους «ογλούδες», είχε ακουστεί σε πολλά σημεία της Ελλάδας, πριν τους αγώνες ομάδων με μικρασιατική προέλευση, εναντίον «γηγενών».
Θα αδικούσαμε όμως πολλούς αν δεν αναφέραμε ότι στα αθλητικά σωματεία, ανεξάρτητα από προέλευση – καταγωγή των μελών τους συνυπήρξαν και δημιούργησαν από κοινού και πρόσφυγες και «γηγενείς».
Στα ιδρυτικά μέλη του Ηρόδοτου, ήταν ο πρόεδρος της κοινότητας Αλικαρνασσού ο γιατρός Μιχάλης Βελισσάριος, ο Δημήτρης Σκουρέλλος, ο Απόστολος Μουζουράκης και αρκετοί άλλοι.
Ο ισχυρός δεσμός με τον τόπο προέλευσης αποτυπώθηκε και σε στίχους του ύμνου της ομάδας, που αναφέρει ότι: «Υπάρχει ένας λαός από τη Μικρασία, που μέσα από τις φλόγες κατάφερε και ζει και τον Ηρόδοτο οδηγεί».
Για να κατανοήσουμε καλύτερα το ιστορικό πλαίσιο μέσα στο οποίο γεννήθηκε και αναπτύχθηκε ο Ηρόδοτος, μεταφέρουμε από το Δήμο Ηρακλείου την ακόλουθη ιστορική αναφορά: «Μετά το 1922, οι Μικρασιάτες δεν θα επιστρέψουν ποτέ στις ιδιαίτερες πατρίδες τους παρά μόνο ως επισκέπτες. Για να κατανοήσουμε πως πραγματοποιείται η μετάβαση από την Παλιά στη Νέα Αλικαρνασσό είναι απαραίτητο να εντάξουμε την μετακίνηση των Αλικαρνασσέων στο γενικότερο προσφυγικό ρεύμα από την Μ. Ασία στην Ελλάδα και ειδικότερα στην Κρήτη.
Οι Μικρασιάτες διώκονται εξαιτίας της εθνικής τους ταυτότητας. Βασική επιδίωξη της τουρκικής πλευράς ήταν α) η εξαφάνιση του ελληνικού στοιχείου από την Μ. Ασία, ώστε να μπορεί να διεκδικήσει τα εδάφη αυτά, επικαλούμενη την εθνική ομοιογένεια του πληθυσμού και β) η ταυτόχρονη αποδυνάμωση του ελληνικού κράτους εξαιτίας της πληθυσμιακής έκρηξης που προκλήθηκε.
O πρώτος διωγμός των Ελλήνων της Μ. Ασίας αρχίζει το 1914. Τότε, παρατηρείται και η σταδιακή άφιξη Μικρασιατών προσφύγων στην Κρήτη και ειδικότερα στο Ηράκλειο. Από το 1915-1919 φιλοξενήθηκαν στο Ηράκλειο γύρω στις 1.500 οικογένειες από τη Μ. Ασία και τα Δωδεκάνησα, συνολικά περίπου 6.000 άτομα. Οι πρώτοι Αλικαρνασσείς πρόσφυγες φτάνουν στην Κρήτη, στη περιοχή της Σητείας και από εκεί στο Ηράκλειο το 1914. Διέμεναν σε παραπήγματα, στην περιοχή της Χανιώπορτας. Απ’ αυτούς λίγοι επιστρέφουν στις εστίες τους την περίοδο 1918 -1919. Το 1921 οι περισσότεροι πρόσφυγες που παραμένουν στο Ηράκλειο είναι από την Αλικαρνασσό και το Αϊδίνι.
Σύμφωνα με τα στοιχεία που προκύπτουν από την πολιτογράφηση των προσφύγων το 1923 στο Ηράκλειο εγκαταστάθηκαν 12.070 πρόσφυγες από τη Μ. Ασία, 325 από τους οποίους κατάγονται από την παλιά Αλικαρνασσό.
Η Ν. Αλικαρνασσός βρίσκεται στο 2,5 χλμ. της κεντρικής αρτηρίας Ηρακλείου – Λασιθίου, στην ανατολική πλευρά του Ηρακλείου. Η γη που παραχωρήθηκε για την ίδρυση του προσφυγικού αυτού συνοικισμού ήταν 6000 στρέμματα με σύνορα από το Βορρά το Κρητικό πέλαγος, από την Ανατολή και το Νότο, τα όρια της επαρχίας Πεδιάδος και από τη Δύση, το Σιλαμιανό ποταμό.
Ο χώρος αυτός τηρούσε όλες τις προϋποθέσεις σύμφωνα με τη Διεύθυνση Εποικισμού ώστε να αναδειχθεί σε νέα πατρίδα για τους ξεριζωμένους «Πετρουμιανούς». Βασικό σημείο για την επιλογή της περιοχής ήταν η παραθαλάσσια επίπεδη θέση της που δημιουργούσε στους Αλικαρνασσείς πρόσφυγες συναισθήματα οικειότητας και αποδοχής και ταυτόχρονα εξασφάλιζε επαγγελματικά πολλούς από αυτούς αφού η κύρια ασχολία τους ήταν η αλιεία.
Η διαδικασία ίδρυσης της Ν. Αλικαρνασσού είχε ξεκινήσει από το 1924. Αρχικά, εξελέγη η «αγροτοαστική ομάδα Αλικαρνασσού», και στις 15/10/1924 προκηρύσσεται διαγωνισμός για την ανέγερση 300 οικιών. Η νέα πόλη είχε χωριστεί σε τρεις ζώνες ανάλογα με τα επαγγέλματα των οικιστών.
Η βόρεια ζώνη τα «θαλασσινά» παραχωρήθηκαν στους αλιείς, η νότια τα «γεωργικά» στους αγρότες ενώ η ενδιάμεση κεντρική ζώνη, τα «αστικά» σε αυτούς που είχαν αναπτύξει αστικές δραστηριότητες, εμπόρους, τεχνίτες, κτίστες, εργάτες.
Το σχέδιο της πόλης είχε καλή ρυμοτομία και προέβλεπε την ολοκλήρωση ελεύθερων χώρων και άνετων δρόμων. Τον αρχικό πληθυσμό της Ν. Αλικαρνασσού αποτελούσαν 350 πολυμελείς οικογένειες με καταγωγή από την Παλιά Αλικαρνασσό ή τα περίχωρα.
Η οικονομική και κοινωνική εξέλιξη της Αλικαρνασσού αποτέλεσε μια δύσκολη πρόκληση για τους Αλικαρνασσείς πρόσφυγες, την οποία αποδέχθηκαν με πείσμα παρόλο που βαθιά στις ψυχές τους πίστευαν πως σύντομα θα ξαναγύριζαν στα μέρη τους, στο Πετρούμι.
Η πίκρα και η νοσταλγία τους, όμως, δεν έδρασαν ανασταλτικά. Με σκληρή δουλειά και ανεξάντλητη ψυχική δύναμη προσπαθούσαν να «αναστήσουν» την χαμένη τους πατρίδα. Η σύγκριση του παλιού και του νέου τόπου τους ήταν διαρκής και τους ωθούσε σε ολοένα μεγαλύτερες θυσίες ώστε η Νέα Αλικαρνασσός να αναδειχθεί σε άξια διάδοχο της Παλιάς».
Ο Ηρόδοτος, υπολειτούργησε στη διάρκεια της Γερμανικής κατοχής, ενώ επανήλθε σε πλήρη δραστηριότητα το 1948. Στα χρόνια που ακολούθησαν ο αθλητικός σύλλογος εκτός από την ποδοσφαιρική ομάδα, ανέπτυξε τμήματα μπάσκετ, στίβου, ποδηλασίας και άλλων αθλημάτων. Στα αξιοσημείωτα ότι έχει ιδιόκτητο γήπεδο.
Στη μεταπολεμική περίοδο εκτός από συμμετοχές στις τοπικές κατηγορίες, συμμετείχε στις εθνικές κατηγορίες, τη Δ’ Εθνική, τη Γ’ Εθνική (19 περιόδους), τη Β’ Εθνική (12 περιόδους) και την τρέχουσα περίοδο Επίσης έχει κατακτήσεις ερασιτεχνικών κυπέλλων της Ε.Π.Σ. Ηρακλείου, αλλά και το Κύπελλο Ερασιτεχνών Ελλάδος της Ε.Π.Ο. 2016-2017, αντιμετωπίζοντας στον τελικό της διοργάνωσης την Ελπίδα Σκουτάρεως, όπως και το SUPER CUP της Ε.Π.Ο. 2016-2017, αντιμετωπίζοντας στον τελικό την Α.Ε. Καραϊσκάκης στο Δημοτικό Γήπεδο Ελευσίνας. Στην τρέχουσα περίοδο αγωνίζεται στη superleague 2.
