Ираклия была заселена с глубокой древности и всегда находилась в сфере влияния соседнего Наксоса. Своё название она получила в честь героя Геракла, а руины эллинистической башни над Ливади свидетельствуют об организованном заселении и укреплениях уже в античную эпоху. Пещера Аи-Яннис, судя по всему, была известна и почиталась ещё с древних времён.
В римскую и византийскую эпохи остров разделял судьбу окружающих Киклад. После Четвёртого крестового похода и падения Константинополя (1204 год) Ираклия вошла в состав венецианского Архипелагского герцогства со столицей на Наксосе.
В годы пиратских набегов, как и большинство малых островов Эгейского моря, Ираклия почти полностью опустела: жители покинули побережье, спасаясь от набегов. На протяжении долгих периодов остров оставался необитаемым, используясь лишь для выпаса скота и земледелия жителями Наксоса и Аморгоса.
Постоянное повторное заселение произошло в XIX веке, когда семьи, в основном с Аморгоса и Наксоса, поселились на острове, живя скотоводством, земледелием и рыболовством. Сегодня Ираклия, с минимальным числом постоянных жителей, остаётся одним из самых нетронутых и подлинных островов всех Киклад.