Η αρχαιολογική έρευνα έχει εντοπίσει μια πρώιμη κυκλαδική εγκατάσταση στο Βαθύ της Αστυπάλαιας που χρονολογείται από την 3η χιλιετία π.Χ., και στην οποία κατά την ελληνιστική εποχή ανεγέρθηκε πύργος. Ένα σύμπλεγμα θολωτών τάφων στο Σύγκαιρο και το Αρμενοχώρι δηλώνουν την παρουσία των Μινωιτών στο νησί και αργότερα των Μυκηναίων (1500 π.Χ. – 1100 π.Χ.). Κατά τους αρχαίους χρόνους, ο κύριος οικισμός με την ακρόπολη βρίσκονταν στο μεσαιωνικό Κάστρο, στη σημερινή Χώρα της Αστυπάλαιας. Η εγκατάσταση στο χώρο αυτό χρονολογείται τουλάχιστον από τον 8ο αιώνα π.Χ. Επίσης, έχουν εντοπιστεί ευρήματα της ελληνιστικής εποχής. Στο κάστρο του Αϊ Γιάννη βρέθηκαν νεκροταφεία των προϊστορικών και των κλασικών χρόνων.
Στους ιστορικούς χρόνους, σύμφωνα με τον Στράβωνα, οι κάτοικοι της Αστυπάλαιας κατέλαβαν το Ροίτειο, μια πόλη της Μικράς Ασίας στο ομώνυμο ακρωτήριο της Τρωάδας, στην έξοδο του Ελλησπόντου. Επίσης ίδρυσαν το Πόλιον στον ποταμό Σιμόεντα στην Τρωάδα που αργότερα ονομάστηκε Πόλισμα. Από το μικρό αυτό νησί του Αιγαίου καταγόταν ο Φάλαρις που πήγε στον Ακράγαντα και έγινε τύραννος. Αστυπαλιώτες ήταν και οι φημισμένοι ολυμπιονίκες Ονησίκρητος και Κλεομήδης για τον οποίο μάλιστα έχει διασωθεί μια τραγική ιστορία, όταν από υπαιτιότητά του κατά την διάρκεια πυγμαχικού αγώνα στην Ολυμπία έχασε τη ζωή του ο Ίκκος από την Επίδαυρο. Από διάφορες επιγραφές μαθαίνουμε ότι η Αστυπάλαια στην αρχαιότητα είχε αναπτυγμένη ναυτιλία.
Το νησί ήταν μέλος της Α’ Αθηναϊκής Συμμαχίας (454-424 π.Χ.), και σύμφωνα με τον φορολογικό κατάλογο του 436 π.Χ. κατέβαλλε στο κοινό ταμείο 12.000 δραχμές. Τον 3ο αιώνα π.Χ. η Αστυπάλαια βρισκόταν κάτω από την επιρροή των Πτολεμαίων. Εξαιτίας της στρατηγικής γεωγραφικής της θέσης στους ναυτικούς δρόμους ανάμεσα στην ηπειρωτική Ελλάδα και το ανατολικό και νότιο Αιγαίο, προσέλκυσε το ενδιαφέρον των Ρωμαίων. Είναι χαρακτηριστικό ότι η ρωμαϊκή Σύγκλητος συνήψε συνθήκη συμμαχίας με το νησί που περιλάμβανε προνόμια αυτονομίας. Από τη Αστυπάλαια ο στόλος των Ρωμαίων απέπλεε για τα καταπολεμήσει τους πειρατές που απειλούσαν την ασφάλεια των νησιωτών και της ναυσιπλοΐας στο νοτιανατολικό Αιγαίο.
Την πρώιμη παρουσία του Χριστιανισμού στην Αστυπάλαια μαρτυρούν στο Λιβάδι τα ερείπια μια τρίκλιτης παλαιοχριστιανικής βασιλικής με ψηφιδωτό δάπεδο του 6ου αιώνα που ήταν αφιερωμένη στον Άγιο Βασίλειο. Το ιερό του ναού καταλαμβάνει σήμερα μια εκκλησία που ονομάζεται Άγια των Αγίων. Επίσης είναι γνωστή μια παλαιοχριστιανική βασιλική στη τοποθεσία Καρέκλη, στην ανατολική ακτή της Μαλτεζάνας. Εκεί βρίσκεται και λουτρό με μωσαϊκό δάπεδο της ίδιας περιόδου.
Μετά την άλωση της Κωνσταντινούπολης από τους Φράγκους της Δ΄ Σταυροφορίας, η Αστυπάλαια δόθηκε το 1207 από τον δούκα της Νάξου Μάρκο Σανούδο στον βενετό Ιωάννη Κουϊρίνι (Giovanni Querini). Το 1269 η Αστυπάλαια ανακαταλήφθηκε από τον ιταλικής καταγωγής βυζαντινό ναύαρχο Λικάριο που πρόσφερε τις υπηρεσίες του στον αυτοκράτορα Μιχαήλ Η’ Παλαιολόγο. Το 1333 το νησί βρέθηκε κάτω από την κυριαρχία του Ιωάννη Β’ Κουϊρίνι, για να καταληφθεί το 1341 από τον εμίρη του Αϊδίνίου Ομάρ Βέη Μορβασσάν. Το 1341 ο οίκος των Κουϊρίνι επανήλθε στην Αστυπάλαια, και το 1413 ο Ιωάννης Δ΄ επεχείρησε να εγκαταστήσει στο νησί νέους αποίκους. Έκανε στη συνέχεια μια δεύτερη απόπειρα που στέφτηκε με επιτυχία, αλλά γενικά τα χρόνια εκείνα το νησί υπέφερε πληθυσμιακά εξαιτίας των οθωμανικών πειρατικών επιδρομών. Ο Κουϊρίνι το 1413, όπως μαρτυρεί η εντοιχισμένη επιγραφή, ανακαίνισε επίσης το τραγουδισμένο κάστρο της Αστροπαλιάς που δεσπόζει στον λόφο πάνω από τη Χώρα και επιβλέπει το λιμάνι. Εκεί στα μεσαιωνικά χρόνια ήταν ο οχυρωμένος οικισμός, ασφαλές καταφύγιο στα πειρατικά κόυρσα. Διέθετε αμυντικό πύργο με στέρνα και αποτελούσε εκτός από κατοικία του ντόπιου ηγεμόνα και την ύστατη γραμμή άμυνας των πολιορκούμενων. Ο πυκνοδομημένος ιστός των «καστρινών» σπιτιών είχε κέντρο τη πλατεία της «Μπλάτσας» που μάλλον βρισκόταν γύρω από τον έξω νάρθηκα του ναού του Αγίου Γεωργίου. Κοντά στο χαμηλό διαβατικό που αποτελεί την πύλη εισόδου στο κάστρο χτίστηκε τον 18ο αιώνα από τον μοναχό Άνθιμο ο ναός της Παναγίας της Πορταΐτισσας ή Παναγιάς του Κάστρου. Από τα μέσα του 19ου αιώνα άρχισε η εγκατάσταση των κατοίκων γύρω από το κάστρο, ενώ στον 20ό αίωνα συνοικίστηκε η πόλη γύρω από το λιμάνι.
Τελικά το 1540 η Αστυπάλαια ενσωματώθηκε στην Οθωμανική αυτοκρατορία ύστερα από συμφωνία με τους Ενετούς. Η τουρκοκρατία στο νησί, όπως και στα υπόλοιπα Δωδεκάνησα, χαρακτηρίζεται από την παροχή προνομίων αυτοδιοίκησης στους νησιώτες. Η Επανάσταση του 1821 βρήκε τους Αστυπαλιώτες έτοιμους να συμμετάσχουν στον εθνικό Αγώνα, και το νησί διοικητικά τότε ανήκε στην επαρχία των Νοτίων Σποράδων της επαναστατικής ελληνικής πολιτείας. Οι ελπίδες των κατοίκων του διαψεύστηκαν όταν το 1830 οι Μεγάλες Δυνάμεις με το Πρωτόκολλο του Λονδίνου τους άφησαν εκτός των ορίων του ελληνικού κράτους. Στην συνέχεια η μοίρα του ταυτίστηκε με αυτών των υπόλοιπων Δωδεκάνησων, αφού οι Ιταλοί το κατέλαβαν στις 23 Απριλίου 1912 κατά τη διάρκεια του ιταλοτουρκικού πολέμου. Ενσωματώθηκε στην Ελλάδα το 1948 ύστερα από μια σύντομη κατοχή από τους Βρετανούς (1945-1947).
