Κατά την μυθολογία, η Αστυπάλαια και η Ευρώπη ήσαν κόρες του Φοίνικος και της Περιμήδης. Από την ένωση της Αστυπάλαιας με τον Ποσειδώνα γεννήθηκε ο Αργοναύτης Αγγαίος και ο βασιλιάς της Κω Ευρύπυλος.
Σύμφωνα με τον Στέφανο τον Βυζάντιο η Αστυπάλαια κατοικήθηκε αρχικά από Κάρες, που πρώτοι την ονόμασαν Πύρρα. Κατά τον Οβίδιο το νησί πέρασε από την κατοχή της Κρήτης, τον καιρό του Μίνωα, ενώ αργότερα εξελληνίστηκε από αποίκους που ήρθαν από τα Μέγαρα. Μεγαρείς αποίκους στην Αστυπάλαια, πατρίδα του ολυμπιονίκη Κλεομήδη, αναφέρει και ο Σκύμνος. Ακόμη, μια επιγραφή του Δ’ π. Χ. αι. που βρέθηκε στο ασκληπιείο της Επιδαύρου αναφέρει τους πρώτους Αστυπαλίτες ως αργολικής καταγωγής.