East of Paleokastro (Sitia Province) rises the steep hill Kastri, which separates the beaches of Kouremenos and Chiona. The hill was called Paleo Castro (Old Fort) by the Venetians, after which the current village is named.
Here, the Venetians built a fortress, probably on the ruins of a preexisting Minoan fort, to protect the bay where the ships docked. However, the fort was abandoned quite soon and in 1668 the Turkish traveler Evliya Celebi reported that it was already ruined. Today almost nothing survives of the fort.