Η Αστυπάλαια πρωτοκατοικήθηκε κατά την αρχαιότητα από τους Κάρες οι οποίοι λόγω του εδάφους της (κοκκινόχωμα) την ονόμασαν Πύρρα. Αργότερα το νησί μετονομασθεί σε Πυλαία, είτε λόγω κάποιου αρχηγού των κατακτητών του νησιού είτε και επικρατέστερα λόγω των πολλών πυλών (κόλπους και όρμους περιμετρικά του νησιού).
Στην αρχαιότητα η Αστυπάλαια ήταν ξακουστή για τα πολλά πολύχρωμα λουλούδια της, για την πλούσια σε καρποφόρα δένδρα γεωργία της, για την κτηνοτροφία της και για το περίφημο μέλι της. Συνεπώς, άκρως δικαιολογημένα την αποκάλεσαν Τράπεζα των Θεών. Οι Ρωμαίοι με τη σειρά τους την αποκαλούσαν Ιχθυόεσσα λόγω των πλουσίων σε ψάρια θαλασσών της, αλλά και των αρίστης ποιότητας σφουγγαριών των βυθών της.
Η σημερινή της ονομασία ως Αστυπάλαια προέκυψε από τους Φοίνικες (παλαιόν άστυ) που χρησιμοποιούσαν το νησί ως εμπορικό σταθμό. Υπάρχει βέβαια και η εκδοχή να οφείλεται σε παλιά πολιτεία της Κω λεγόμενη Αστυπάλαια, η οποία μετά την καταστροφή της από μεγάλο σεισμό οι κάτοικοί της μετοίκησαν σε αυτό το νησί δίνοντας του το όνομα της παλιάς τους πατρίδας.
Τον 13ον και 14ον μ.χ. αιώνα το νησί αποκτά και νέον όνομα, Αστυνέα, από τη βενετσιάνικη οικογένεια των Κουερίνοι (Quirines) οι οποίοι επί τρεις αιώνες κυριαρχούσαν το νησί και οι απόγονοί τους ως ανάμνηση της παλιάς τους δόξας κρατούν τον τίτλο τους και υπογράφουν ως Quirini-Stampaglia. Το νησί ονομάσθηκε αργότερα και Αστροπαλιά λόγω της λάμψης που είχε κατά την αρχαιότητα ως άστρο σε ζοφερούς χρόνους και σύμφωνα με άλλους λόγω του μοναδικά έναστρου ουρανού του τις ξάστερες νύχτες.
Οι κάτοικοι του νησιού αρέσκονται και στα δύο ονόματα (Αστυπάλαια και Αστροπαλιά) και για αυτό προσφωνούνται ως Αστυπαλίτες ή Αστροπαλίτες.