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