Η Ηρακλειά, όπως και οι υπόλοιπες Μικρές Κυκλάδες, κατοικήθηκε από την προϊστορική εποχή και διατηρεί το όνομά της από την αρχαιότητα.
Στις θέσεις Κάμπος Αγίου Αθανασίου και Άγιος Μάμας, έχουν βρεθεί λείψανα δύο οικισμών και νεκροταφείου, που ανήκουν στην 3η χιλιετία π.Χ., ενώ στην περιοχή του Κάστρου έχει διαπιστωθεί η ύπαρξη ιερών της θεάς Τύχης και του Λοφίτου Διός.
Επίσης σε διάφορα σημεία του νησιού, έχουν βρεθεί εργαλεία οψιδιανού, πετρώματος που υπήρχε στη Μήλο, γεγονός που μαρτυρά τη συμμετοχή του νησιού στις εμπορικές δραστηριότητες της περιοχής κατά την Πρωτοκυκλαδική περίοδο.
Η ακριβής χρονολόγηση του ερειπωμένου φρουρίου που σώζεται σε λόφο στη θέση Κάστρο, δεν έχει αποσαφηνιστεί, ωστόσο στο εσωτερικό του διακρίνονται ίχνη κατοίκησης ελληνιστικών και ρωμαϊκών χρόνων.
Στη διάρκεια της οθωμανικής περιόδου, οι κλειστοί και δυσπρόσιτοι ορμίσκοι του νησιού, έγιναν ιδανικά καταφύγια για τους πειρατές, οι δραστηριότητες των οποίων εκείνη την περίοδο καθόρισαν σε μεγάλο βαθμό την καθημερινότητα και τις συνήθειες των κατοίκων.
Από τον 16ο αιώνα, η Ηρακλειά υπάγονταν διοικητικά και ιδιοκτησιακά στη Μονή Χοζοβιωτίσσης της Αμοργού, που το 1831 επέτρεψε σε Αμοργιανούς να έρθουν στο νησί, υπογράφοντας μαζί τους συμβόλαιο δεκαετούς διάρκειας με δικαίωμα κατοχής και εκμετάλλευσης της γης και κατανομής των προϊόντων κατά 50%.
Το καθεστώς αυτό με διάφορες διοικητικές αλλαγές κράτησε μέχρι την απαλλοτρίωση των μοναστηριακών περιουσιών από την κυβέρνηση Νικολάου Πλαστήρα, οπότε και δόθηκαν οριστικά στους ενοικιαστές οι καλλιεργήσιμες εκτάσεις, αφήνοντας στη μονή όσα χρειάζονταν για τις ανάγκες των μοναχών.
Μετά την επανάσταση του 1821 η Ηρακλειά εντάχθηκε στο νεοσύστατο ελληνικό κράτος, όπως και τα υπόλοιπα νησιά των Κυκλάδων.
Κατά τη διάρκεια της κατοχής των ελληνικών εδαφών από τις Δυνάμεις του Άξονα, η Ηρακλειά αρχικά υπαγόταν στην ιταλική διοίκηση, ενώ μετά τη συνθηκολόγηση της Ιταλίας το 1943, πέρασε στη γερμανική κατοχή ως την απελευθέρωσή της, το 1944.
Ο ρόλος της Ηρακλειάς στην αντίσταση ήταν σημαντικός, καθώς υπήρχε στο νησί ασύρματος που μετέφερε μηνύματα για τις κινήσεις των Γερμανών προς τις συμμαχικές δυνάμεις.
