Ένας  από τους ποιο σημαντικούς αρχαιολογικούς χώρους του νησιού, είναι το κατεστραμμένο φρούριο της Παλαιόχωρας, η βυζαντινή πρωτεύουσά του. Χτίστηκε από Μονεμβασίτες το 12ο αιώνα όπου ονομάστηκε πόλη του αγίου Δημητρίου και βρίσκεται στη βόρεια πλευρά του νησιού ανάμεσα σε ένα φυσικό οχυρό μέσα σε ένα άγριο βαθύ φαράγγι καλυπτόμενο από τεράστια βράχια. Το φαράγγι καταλήγει στην ακτή της Κακιάς Λαγκάδας. Εκεί προστατευόντουσαν οι κάτοικοι από τις επιδρομές των πειρατών. Η πολιτεία καταστράφηκε το 1537 από τον αρχιναύαρχο του τούρκικου στόλου Χαϊρεντίν Μπαρμπαρόσα τη "μαύρη φοβέρα" του αρχιπελάγους, ο οποίος κούρσεψε την πολιτεία, κατάσφαξε πολλούς κατοίκους, πυρπόλησε και ρήμαξε την άλλοτε ζωντανή πρωτεύουσα η οποία από τότε δεν ξανακατοικήθηκε ποτέ πια. Εάν ξεναγηθείτε μέσα στο φρούριο  θα παρατηρήσετε μερικές εκκλησίες μία από αυτές είναι ο ναός της Αγίας Βαρβάρας εξαίρετο δείγμα μονεμβασιώτικης αρχιτεκτονικής. Ένας μύθος για την Παλαιόχωρα λέει ότι αργά το βράδυ ακούγονται οι φωνές των γυναικών την ώρα της σφαγής! Εάν είστε αρκετά τολμηροί και αγαπάτε την φύση και έχετε και ορειβατικό εξοπλισμό μπορείτε να κατεβείτε το φαράγγι και να καταλήξετε στην θάλασσα!