In Greek mythology, Astypalaia was a woman abducted by Poseidon in the form of a winged fish-tailed leopard. It was colonized by Megara, and its constitution and buildings are known from numerous inscriptions. The Roman emperors recognized it as a free state.

During the Middle Ages it belonged to the Byzantines until 1207, when - in the aftermath of the Fourth Crusade - it became fee of the Querini, a noble Venetian family, until 1522. The Querini built a castle that is still in place and added the name of the island to their family name, that became Querini Stampalia. Astypalea became Turkish in 1522, and the Ottomans kept it until 1912, with only two interruptions: from 1648 until 1668, during the War of Crete, it was occupied by Venice, and from 1821 to 1828 it joined the insurgents during the Greek War of Independence.

Occupied again by the Ottomans in 1828, on April 12th, 1912, (during the War of Libya) a detachment of the Regia Marina landed on Astypalea, which became so the first island of the Dodecanese to be occupied by Italy. From there the Italians, on the night between 3rd and 4th of May, landed on Rhodes. The island remained under Italian governance until WWII. In 1947, together with the whole Dodecanese, it joined Greece.