Η Ηρακλειά κατοικείται από τα βάθη της αρχαιότητας και ανήκε πάντα στη σφαίρα επιρροής της γειτονικής Νάξου. Το όνομά της αποδίδεται στον ήρωα Ηρακλή, ενώ τα ερείπια του ελληνιστικού πύργου πάνω από το Λιβάδι μαρτυρούν οργανωμένη κατοίκηση και οχύρωση ήδη από την αρχαία εποχή. Το Σπήλαιο του Αϊ-Γιάννη φαίνεται πως ήταν γνωστό και λατρευτικό από τα αρχαία χρόνια.
Κατά τους ρωμαϊκούς και βυζαντινούς χρόνους το νησί ακολούθησε την τύχη των γύρω Κυκλάδων. Μετά την Τέταρτη Σταυροφορία και την άλωση της Κωνσταντινούπολης (1204), η Ηρακλειά εντάχθηκε στο Δουκάτο του Αιγαίου των Ενετών, με έδρα τη Νάξο.
Στα χρόνια της πειρατείας, όπως και τα περισσότερα μικρά νησιά του Αιγαίου, η Ηρακλειά ερήμωσε σχεδόν εντελώς: οι κάτοικοι εγκατέλειψαν τις ακτές για να γλιτώσουν από τις επιδρομές. Για μεγάλες περιόδους το νησί έμεινε ακατοίκητο, χρησιμοποιούμενο μόνο για βοσκή και καλλιέργειες από κατοίκους της Νάξου και της Αμοργού.
Η μόνιμη επανακατοίκηση ήρθε κατά τον 19ο αιώνα, όταν οικογένειες κυρίως από την Αμοργό και τη Νάξο εγκαταστάθηκαν στο νησί ζώντας από την κτηνοτροφία, τη γεωργία και το ψάρεμα. Σήμερα η Ηρακλειά, με ελάχιστους μόνιμους κατοίκους, παραμένει ένα από τα πιο ανέγγιχτα και αυθεντικά νησιά όλων των Κυκλάδων.