Κατά την μυθολογία, η Αστυπάλαια και η Ευρώπη ήσαν κόρες του Φοίνικος και της Περιμήδης. Από την ένωση της Αστυπάλαιας με τον Ποσειδώνα γεννήθηκε ο Αργοναύτης Αγγαίος και ο βασιλιάς της Κω Ευρύπυλος.
Σύμφωνα με τον Στέφανο τον Βυζάντιο η Αστυπάλαια κατοικήθηκε αρχικά από Κάρες, που πρώτοι την ονόμασαν Πύρρα. Κατά τον Οβίδιο το νησί πέρασε από την κατοχή της Κρήτης, τον καιρό του Μίνωα, ενώ αργότερα εξελληνίστηκε από αποίκους που ήρθαν από τα Μέγαρα.
Κατά την ελληνιστική εποχή η Αστυπάλαια υπήρξε λιμάνι – σταθμός των Πτολεμαίων της Αιγύπτου και υποστηρίζεται ότι αυτή την περίοδο ιδρύεται στο νησί νομισματοκοπείο , ενώ κατά την ρωμαϊκή περίοδο παρουσίασε σημαντική ακμή, χάρις στα πολλά φυσικά λιμάνια που αποτελούσαν ορμητήριο κατά των πειρατών.
Κατά την βυζαντινή εποχή τα νησιά του Αιγαίου Πελάγους – του “Αρχιπελάγους” - έπαιξαν τον ρόλο ναυτικών βάσεων με στρατηγική σημασία ως προς τον έλεγχο των διεθνών διελεύσεων. Η Αστυπάλαια υπάγεται κι αυτή στο “ θέμα του Αιγαίου”, στην βυζαντινή δηλαδή επαρχία των Κυκλάδων.
Με την άλωση της Κωνσταντινούπολης και την κατάλυση του Βυζαντινού κράτους από τους Φράγκους, το 1204, οι Κυκλάδες και τα άλλα νησιά του Αρχιπελάγους περιέρχονται στην δικαιοδοσία της Βενετίας. Η Αστυπάλαια, κατά τον G. Gerola, παραχωρήθηκε το 1207 από τον Δούκα του Αρχιπελάγους Marco Sanudo στον Ενετό ευγενή Τζοβάνι Ι. Κουερίνι σε ανταπόδοση των υπηρεσιών του τελευταίου κατά την ίδρυση του νέου δουκάτου. Ο Querini θεωρήθηκε έτσι, ως ο ιδρυτής και πρώτος ιδιοκτήτης μιας οίκησης, που αποτέλεσε τον πυρήνα του σημερινού οικισμού.
Οι επιδρομές και οι αρπαγές των Τούρκων κατά τον 14 αι., δεν περιορίζονται στο Αιγαίο, όπου η πειρατεία ήταν το γενικό φαινόμενο, αλλά επεκτείνονται μέχρι και το Ιόνιο. Από τα παράλια λοιπόν της Μ. Ασίας, ιδίως από το εμιράτο του Μεντεσέ, “πραγματική φωλιά πειρατών, πλέουν οι Τούρκοι στα απέναντι Δωδεκάνησα, αρπάζουν κοπάδια, σοδειές και αιχμαλωτίζουν τους κατοίκους”. Η συνεχώς αυξανόμενη παρουσία των Τούρκων αναγκάζει τη Βενετία σε αναθεώρηση της πολιτικής της, της σχετικής ανεξαρτησίας των διαφόρων αρχόντων, και σε ανάληψη άμεσης διοίκησης. Έτσι η δυναστεία των Γκύζη της Τήνου και Μυκόνου σβήνει το 1390, το Δουκάτο της Νάξου όμως εξακολουθεί την ανεξάρτητη πορεία του.
Ο Goavanni IV – Zannaki Querini πεθαίνει το 1421 και ο διάδοχος του, Giovanni, πάλι Querini, αποκτά το 1446 το ένα τέταρτο της Αμοργού, με παραχώρηση από την Βενετική διοίκηση. Η συνιδιοκτησία της Αμοργού από τους Querini και τους Grimani πιστοποιεί τις σχέσεις των δύο οικογενειών, που, κατά τον Gerola, ανάγονται στην εποχή του Giovanni II Querini και την κοινή τους προσπάθεια ανάκτησης της Αστυπάλαιας. Με τον θάνατο του Giovvani Querini, η Αστυπάλαια και η νέα κτήση της Αμοργού περιέρχονται στον Francesco, γιο του Giovanni – Zanaki Querini, υπό την κυριαρχία του οποίου ο πληθυσμός της Αστυπάλαιας ανέρχεται το 1470 σε 400 μόλις άτομα. Το 1494 καταλύεται η ανεξαρτησία του δουκάτου της Νάξου, στα πλαίσια της αμεσότερης ανάμειξης της Βενετίας στο Αιγαίο, η προσπάθεια όμως δεν απέτρεψε την Οθωμανική εξάπλωση.
Από το 1537 έως το 1566 το νησί αυτοδιοικείται από το Συμβούλιο δημογερόντων, εκλεγόμενο με δικαστική, δημοσιονομική και διοικητική εξουσία. Το 1566, επί της εποχής του γιου του Σουλεϊμάν Α', του Σελίμ του Β', καταλύεται και το εναπομένον Δουκάτο του Αιγαίου και αποδίδεται στον Εβραίο τραπεζίτη, ευνοούμενο του Σουλτάνου, Ιωσήφ Νάζη. Η Αστυπάλαια είναι ένα από τα νησιά που περιλαμβάνονται στη δικαιοδοσία του. Νέα ένταση της αναρχίας στο Αιγαίο σημειώνεται κατά τον 17ο αι., με τις επιδρομές κυρίως Δυτικοευρωπαίων καθολικών πειρατών, κυρίως Γάλλων στην υπηρεσία του δούκα της Τοσκάνης. Τον 18ο και τον 19ο αιώνα η οικονομία των νησιών ακολουθεί μια ανοδική πορεία με παράλληλη άνοδο του πληθυσμού. Η Αστυπάλαια με γεωργοκτηνοτροφική κυρίως παραγωγή παρουσιάζει μια εμπορική δραστηριότητα, στην περιφέρεια όμως της Σύμης και της Καλύμνου. Στις 4 Μαΐου 1823 οι Αστυπαλίτες κατήργησαν την οθωμανική κυριαρχία και έλαβαν μέρος στην Ναυμαχία του Γέροντα. Κατά την διοικητική διαίρεση του 1828, που έγινε από τον Καποδίστρια, περιελήφθη στο νέο ελληνικό κράτος, αργότερα όμως με το πρωτόκολλο των Προστάτιδων Δυνάμεων του 1830 αποδόθηκε στην Οθωμανική Αυτοκρατορία.
Στο διάστημα του 1830 – 1870 η οικονομία του νησιού αναπτύσσεται, με την ισχυροποίηση του διαμετακομιστικού εμπορίου, η βιομηχανική όμως επανάσταση στην Ευρώπη και η καταστροφή του περίφημου εμπορίου της Ανατολής αναστατώνουν τις δομές της Οθωμανικής Αυτοκρατορίας με βαριές συνέπειες για το νησί.
Τον Απρίλιο του 1912 κατά τον Ιταλοτουρκικό πόλεμο, το νησί καταλαμβάνεται από την Ιταλία, μέχρι τον Μάρτιο του 1948, οπότε παραχωρείται στην Ελλάδα, μαζί με τα άλλα Δωδεκάνησα.