The village of Kali Limenes is located east of cape Lithino, south of Asterousia.

According to the text of the acts of the Apostles (27,8), the Apostle Paul, during his transportation to Rome to be tried, passed by the southern coast of Crete, and disembarked due to strong winds at the safe anchorage of Kali Limenes. The presence of Saint Paul is associated with the spread of Christianity and the establishment of basilicas in the early Christian times in southern Crete, specifically in Asterousia.

In 1911 a small church dedicated to the memory of Apostle Paul was built on the spot of an old basilica, on a hill south of the modern port. Next to the temple, according to tradition, is the cave where Paul stayed.