On the island Astypalaia are quite a few beaches and since it is fairly quiet, there are plenty of opportunities for naturists. Some beaches (eg Tzanaki and Agios Konstantinos Beach) are seen as a naturist beach, but there are many more bays and beaches (eg Vai and Plakes) where naturists are found, sometimes mixed with people that are wearing a swimsuit.
Most visitors to the island will during their vacation stay in the port Pera Gialos, in the overlying Chora, or near Maltezana Beach or Livadi Beach, because all the accommodations of the island are here, but those who rent a moped or hire a good car (most roads on the island are dirt tracks) or those that take the trouble to walk, will discover a lot of other beaches on Astypalaia.
On the left is a map by Google that basically shows you the location most of the beaches you can find on Astypalaia, but below I've made separate maps because it is easier in case you might want to print the page to take with you on vacation.
The beach of Livadi is an organized beach with parasols and sunbeds for rent. Livadi is the main tourist center of the island and you can find shops, a mini-market and different kinds of accommodations and restaurants here.
Along this stretch of coastline several other more quiet beaches and coves can be reached on foot.
Just south of Livadi in the next cove (Pountari Bay) you will find another smaller beach, Agios Vasilios Beach. Here naturism is not allowed. The people that are looking for a naturist beach have to make a longer walk south past a house with a big pool and then take the path on your left hand side after about 600 meter (the white line on my map). This path leads to the small pebble beach of Tzanaki. The pebbles are quite large though here. In the next cove there is another (smaller) beach where there is also room for naturistst. The walk to Tzanaki Beach takes about 30 minutes.
The town with its white houses and the church of Agios Nikolaos with its blue dome is shaped like an amphitheater and built covering the hillside. It's hard to notice the boundary between Pera Gialos and the Chora above. Chora and Pera Gialos are the two largest villages on the island and they are connected by stairs. For a long time Pera Gialos was the main port and all the ferries that sailed in from other islands to Astypalaia made a stop here. Now only the summer excursion boats leave from the port. Since some time there is a new port on the north side of Astpalaia where the large ferries call on the island.This means that the beach and the water in Pera Gialos are much cleaner now.
Just north of Pera Gialos and within walking distance there are a couple more small beaches.
The village of Maltezana behind the beach consists of Cycladic style built white cubic houses with colored balconies, and a couple of small churches. In the gardens at the homes flowers, citrus trees and vines are grown. Much like Pera Gialos, Maltezana is situated in a fertile valley (this valley is called Mesa Nisi). In the bay the colored wooden boats of fishermen are floating on the water.
Not far from the beach are the well-preserved Tallaras baths dating from the Hellenistic period. There are blue and red-terracotta mosaics with images of the constellations and the seasons of the year. They date from the 5th century AD.
Within walking distance of Maltezana Beach there are some other beaches. Plakes Beach is actually just some rocks from where people enter the water. Mple Limanaki Beach is a tiny beach with gray pebbles, hidden behind a rock wall. The water is beautifully clear.
The larger beach of Vai is located on the north side of Astypalaia and can be reached via a path (you could also go with a good car or a moped). All these beaches are quite secluded and quiet and provide an opportunity for naturists. In high season it seems it's a mixed affair at Vai beach, where some people wear swimwear and naturist don't, and nobody is bothered. It remains quiet. Of course there are no facilities at these beaches, so you will have to bring your own water and food.
Psili Ammos Beach (meaning: fine sand) on the north side of the island is only accessible by boat because the way to it is very bad / dangerous. It is a beach with some stretches of sand and with pebbles on other pieces. The beach is surrounded by an inhospitable rocky landscape.
At seven kilometer distance from the Chora lies Agios Konstantinos Beach. The beach takes its name from a small church that stands on a hill above it. Agios Konstantinos is a long and sandy beach with some facilities (a taverna, beach beds and parasols for rent) during the high season. The beach is also popular with naturists. Agios Konstantinos Beach is easy to reach by car or in about an hour on foot from Livadi. The beach is more or less naturally divided into two parts, with on the southern part the taverna and the beach beds (as of June) and on the northern side the naturists. There are plenty of trees for those that are seeking shade. There are nice views to the Chora and its castle from Agios Konstantinos Beach and it doesn't get too crowded.
At short distance south of Vatses Beach jus around the corner, is another small beach that you can swim to. Not far from Vatses Beach is the Negro Cave that was used as a shelter by pirates in the Byzantine period. Some objects that were found here are exhibited in the Archaeological Museum in Pera Gialos (mainly coins). The caves are accessible by boat.
Just north of Vatses Beach is Kaminakia Beach, where in the high season there are some facilities (sunbeds, umbrellas, tavernas). It is a beach with pebbles in some places and in other places sand. You can go to Kaminakia Beach with an excursion boat, but it can also be reached on foot or with a good car. On the south side of the beach are the trees and the beach beds. Behind the beach are some buildings.
About Panormos Beach I can not find much info. It is located in an enclosed bay and there is a path leading to it. There are no facilities. On the beach there are a number of trees. Pachia Ammos Beach (meaning thick sand), also located in the northwest of Astypalaia, is accessible via an asphalt road nowadays. It is a quiet beach with no facilities. In the vicinity of the beach are some houses and there are trees on the beach to sit in the shade.
Agios Andreas was a small fishing village in the north of Astypalaia. Today it houses the new port of Astypalaia where ferries to the other islands in the Dodecanese and to Piraeus make a stop. Near the village, west of it is a sandy beach, which can be reached over a dirt track. Agios Andreas gets its name from a small church that stands here on top of a cliff.
Steno Beach is a beautiful sandy beach which lies a few kilometers east of Chora, on the south side of the island, in the part where Astypalaia is at its narrowest. The water is shallow and it is easy to go into the sea.
The best and most popular beach of the island of Astypalaia is the beach of Livadi, which is situated close to the harbour of Pera Gialos, just over the hill. The distance to the Chora (the capital on the top of the hill) is 3 kilometers. Livadi is a long beach with citrus orchards in its back. The beach consists of sand and small pebbles. The plain behind Livadi Beach is fertile and the gardens of the village have vines, orange and mandarine trees and all kinds of flowers.
Also at the port of Pera Gialos there is a beach. It is a small sandy beach where you cannot rent beach beds or umbrellas. On the beach you look out over the harbour with its boats.There are a number of trees on the beach though for those who want to lie in the shade. In the harbor of Pera Gialos there are all kinds of amenites, such as an ATM machine and different kinds of shops and restaurants.
There is also an Archaeological Museum where excavations are exhibited from prehistoric times to the Middle Ages. It includes pottery, jewelry, coins, inscriptions and bronze and stone tools from the Mycenaean period.
Maltezana Beach or Analipsi Beach is situated at a distance of 9 kilometers east of the Chora of Astypalea. It is said to have been named after Maltese pirates that once sought shelter in its bay and had a basis here.
There is also a memorial to the French admiral Bigot that set fire to the powder room of his ship in 1827 in order to commit suicide. He preferred death over the dishonor to be captured by pirates.
On top and around the memorial there are remains of pillars dating from the ancient period of the island.
Maltezana is a long and narrow beach with sand and a few pebbles, where you can find shade under the tamarisk trees. From the beach you look out over several small islets that lie in front of the coast of Astypalaia. On Maltezana beach there are umbrellas and sunbeds available.
Maltezana is situated close to the airport of Astypalaia, but let that not scare you off. It is not an international airport, so I estimate that there are no more than one or two flights a day landing and taking off here.
Nearby the beach of Maltezana there are more small bays where it is possible to go into the sea. In high season there are boats leaving from Matezana beach to various bays and beaches in the area and to islets and to islets like Chondro, Ligno, Agia Kiriaki, Koutsomyti, Syrna and Kounoupi (the last name meaning "musquito island").
On the islets of Koutsomyti and Kounoupi you find a pretty beach. The one of Kounoupi is pretty special. It lies in between the two parts of the island and connects them to eachother. The trip to Kounopi island with an excursion boat takes about an hour.
South of Livadi Beach below the beaches of Agios Vasilios and Tzanaki there are a number of other beaches. The first beach is called Papou Beach, the next beach Moura Beach. It seems to be difficult to find these beaches if you want to go to them by land. To Papou beach there is, as far as I can see, no path, but you could try Moura Beach. At some point as you head towards the south you arrive at some kind of crossroads. You can go straight on (to Agios Konstantinos Beach), go to the right into the inland of Astypalaia, or go to the left towards the coast. This path seems to be leading to Mouri Beach. It's possible that these beaches can only be reached by boat.
In the southwest of Astypalaia are Vatses Beach, Kaminakia Beach and Ai Ioannis Beach, in the northwest you can find Pachia Ammos, Agios Andreas and Panormos Beach.
Vatses Beach in the southwest can be reached over an unpaved road or by excursion boat from Pera Gialos. Vatses is a long and wide pebble beach. In high season you can, it seems, rent beach beds and parasols here and there is a taverna that is open. The small beach taverna is there in high season, the beach beds I doubt, as I see it it consists of just a few umbrellas and that's it. There are a number of trees on the beach though in case you want shade. The beach can lie a bit in the wind.
Agios Ioannis Beach is named after the beautiful church that stands on top of a hill near the beach, the Agios Ioannis Prodromou. It is built in the shape of a cross with a dome in the middle. Both the dome and the roofs are painted light blue. In front of the church are fields with citrus trees and below is the beautiful beach. On the right side of the church on a mountain are remains of a castle. On Agios Ioannis Beach there are as far as I know no facilities. The beach can be reached on foot or by boat.
Vathi Beach is located in an enclosed bay in the northeast of Astypalaia, 21 kilometers from the Chora. The opening to the sea is only about 50 meters wide. Vathi Beach is one of the most isolated beaches on the island. It is a pebble beach and the water is shallow. It looks somewhat like a lagoon. At the beach there are a couple of buildings and there are some tavernas and some rooms for rent. Vathi itself is a fishing village where the past, when there was too much wind at Pera Gialos, the ferries docked (when the port of Agios Andreas was not ready yet).