Der Name der Insel wird von der mythischen Gestalt Astypalaia abgeleitet,[1] kann aber auch einfach mit „alte Stadt“ (von altgriechisch ἄστυ ‚Stadt‘ und παλαιός ‚alt‘) übersetzt werden. Im Ostteil der Insel, besonders an der Bucht Vathy, sind frühkykladische Siedlungen nachgewiesen, im Westteil wurden mykenische Kammergräber gefunden.

Am südwestlichen Rand des Hauptortes Chora wurde an der Ausgrabungsstätte Kylindra der größte antike Kinderfriedhof mit den Gebeinen von 2400 Säuglingen und Kleinkindern freigelegt. Zudem gibt es den antiken Friedhof Katselos für Erwachsene und ältere Kinder am benachbarten Hügel.

Im 5. Jahrhundert v. Chr. gehörte Astypalea zum Attischen Seebund. Die antike Polis lag an der Stelle der heutigen Chora. Im Altertum war die Insel bekannt für ihren Fischreichtum. Im 3. Jahrhundert v. Chr. stand sie unter der Herrschaft der Ptolemäer. 105 v. Chr. unterzeichneten die Einwohner des Hauptortes der Insel mit Rom einen Vertrag, der ihnen einen besonderen Status gewährte. Auch in der römischen Kaiserzeit behielt es seine Autonomie.

Von 1207 (Aufteilung des Byzantinischen Reiches nach dem Vierten Kreuzzug) gehörte die Insel – mit einer Unterbrechung Ende des 13. Jahrhunderts – 330 Jahre lang der venezianischen Adelsfamilie der Querini. Nach mehrfacher Plünderung durch Piraten, die die Insel entvölkerten und veröden ließen, wurde die Stadt Anfang des 15. Jahrhunderts von Siedlern aus Tinos neu gegründet.

Chaireddin Barbarossa eroberte 1537 Astypalea für das Osmanische Reich. 1658 war Astypalea während des Krieges um Kreta venezianische Flottenbasis. Der italienische Name der Insel lautete „Stropalia“ oder „Astropalia“.

1821 beteiligten sich die Seefahrer von Astypalea am griechischen Befreiungskrieg, jedoch wurde die Insel unter Selbstverwaltung 1832 wieder dem Osmanischen Reich angeschlossen. 1912 kam sie unter italienische Herrschaft und erst 1947 zusammen mit dem Dodekanes zu Griechenland.