According to one legend, Astipalaia was named after the wife of Neptune. Another legend claims that the island was named after the sister of Europe (the mother of King Minos). The island was called "Ichthioessa" in ancient times, because it was a significant fishing land (fish:ichthis), while it was also called the Altar of the Gods, as it was fertile, with a lot of flowers. The Venetians called the island "Stambalia". The first inhabitants of the island were Kares, while the Cretans later migrated here. From a sign and the dialect from ancient inhabitants, one concludes that emigrants from Argolida lived here, while other signs indicate that the island thrived on sailing. Astipalaia was the homeland of the famous athlete, Kleomedes, who, according to myth, defeated an athlete called Eccos in wrestling in the first Olympian championship, by killing him with a single punch. The judges took away his Olympic title and forced Kleomedes to pay a fine, since they did not consider the death of his opponent legal. Kleomedes, bitter, returned to Astipalaia, and demolished the column of a school, thus causing the death of 60 students. The locals persecuted him by throwing stones, and Kleomedes sought refuge in the Temple of Athena and locked himself in a case. When people of Astipalaia opened the case, they discovered it was empty and Pythia told them that Kleomedes was no longer mortal and was to be honoured as a hero.

Astipalaia was a member of the Athenian Alliance during 454-424 BC, while, due to its naval significance, it had an important role during the Hellenistic Era. In 105 BC, the Romans, after coming to an agreement with the islanders, granted the locals autonomous privileges, in return for the use of the island's ports, which served as refuges from the pirates. There is no significant information concerning the early Byzantine years, yet, after the collapse of the Byzantine Empire, Astipalaia came under the command of the Venetian, Jeremiad Gisi, followed by the Quirini family who, with the exception of a short period of time, ruled the island until 1537, when it was conquered by the Turks. The people of Astipalaia participated in the Greek Revolution in 1821, while the island became part of the "Scheme of Thera", the following year. In spite of Kapodistrias's efforts, Astipalaia and the rest of the Dodecanese island remained under Turkish rule until 1912, when the island was occupied by the Italians, during the Italian-Turkish War (1911-1912). The Italian Rule ended after the end of the World War II, and Astipalaia, along with the rest of the Dodecanese islands, was united with Greece on 7 March 1948.