 Leonidio is situated near the ancient city of Prasiae, which was an important harbour for Sparta until its ruin by the Athenians during the Peloponnesian War.The ancient Greek traveller Pausanias describes the area as the "garden of Dionysus", because of the fertility of its plain, and in ancient myth the young Dionysus was found on its beach and later brought up in a cave emerging from it.There is also a second variant of the story, influenced by Christian tradition, recounting the finding of the relics of Saint Leonides atop the beach of Leonidio, where a church was to be built in his honour, remaining to this day; this is a common suggestion for the derivation of the area's name.