La fortezza distrutta di Paleochora è uno dei più importanti luoghi archeologici dell'isola. È stato costruito dagli abitanti di Monemvasia nel XII secolo è una città bizantina con il nome San Demetrio e si trova nel nord dell'isola tra una fortezza naturale ed una forra. La forra va a finire nella costa di Kakia Lagada. Li andavano gli abitanti per proteggersi dalle invasioni dei pirati. La città è stata distrutta nel 1537 dal turco Ariadeno Barbarossa, la paura dei mari, il quale ha ucciso molti abitanti e ha messo a fuoco la capitale che fin ora era piena di vita. D' allora non l'hanno mai più abitata. Se entrate nel castello vedrete tante chiese, una di queste è il tempio di Santa Barbara, un esempio straordinario dell'architettura di Monemvasia. Un mito dice che a Paleochora, la notte si sentono le voci delle donne quando le ammazzavano! Se avete il coraggio, se amate la natura e se avete equipaggiamento alpinistico potete scendere il burrone che porta al mare!