East of Palaiokastro at the easternmost coast of Crete, in the region of Sitia, rises the steep hill “Kastri”, which separates the beaches of Kouremenos and Chiona. The castle was called Paleo Castro (Old Castle) by the Venetians. Its name was “Rizokastro” before.

Here, the Venetians built a fortress, probably on the ruins of a preexisting Minoan fort and certainly on an existing Byzantine castle.The fort was abandoned early, before the conquest of Crete by the Ottomans in the 17th century. In 1668, the Turkish traveler Evliya Çelebi reported that it was already ruined. Today almost nothing remains of the fort.