Σε ένα από τα πιο αμφιθεατρικά σημεία του νησιού, σε υψόμετρο 253μ. βρίσκεται το βουνό Παλαιόκαστρο. Απέχει τρία χιλιόμετρα από την παραθαλάσσια περιοχή της Σκάνδειας. Το Παλαιόκαστρο απλώνεται σε μια έκταση 145 στρεμμάτων και κατά τον Θουκυδίδη σε αυτήν την περιοχή ήταν κτισμένα τα “Άνω Κύθηρα”. Στην κορυφή του βουνού, μετά από ανασκαφές του Μανώλη Πετρόχειλου, βρέθηκαν τα θεμέλια ιερού ναού της θεάς Αθηνάς. Τα κοσμήματα, ειδώλια και άλλα αντικείμενα που ανασκάφηκαν εκτίθενται στο Αρχαιολογικό Μουσείο Κύθήρων.

Πιο κάτω βρίσκεται χτισμένη η εκκλησία των Αγίων Αναργύρων Κοσμά και Δαμιανού (7ος αιώνας μ.Χ). Εσωτερικά και εξωτερικά του χριστιανικού ναού παρατηρούμε εντειχισμένα αρχιτεκτονικά λείψανα που προέρχονται από αρχαιό ναό. Μετά την ανεύρεση ανάγλυφης αφιερωματικής στήλης, θεωρείται ότι στο σημείο υπήρχε ιερός ναός των Διόσκουρων Κάστορα και Πολυδεύκη. Οι Διόσκουροι μετετράπησαν στους Αγίους Αναργύρους κατά τους χριστιανικούς χρόνους. Στο χριστιανικό ναό βρίσκονται ενσωματωμένα υπολείμματα από κίονες μαζί με πώρινα αρχαïκά κιονόκρανα καθώς και ογκώδεις πώρινοι κυβόλιθοι και μέρος επιστυλίου με σταγόνες.

Ο διάσημος αρχαιολόγος Σλήμαν που επισκέφθηκε τα Κύθηρα στα τέλη του 19ου αιώνα διατύπωσε τη γνώμη ότι ο ναός της Αφροδίτης, ο οποίος θα παρήκμασε κατά τους πρώτους χριστιανικούς αιώνες και σιγά σιγά εξαφανίσθηκε μαζί με το ξόανο της θεάς, θα πρέπει να βρισκόταν στο ίδιο σημείο ή κάπου εκεί κοντά. Σε απόσταση 400 μέτρων δυτικά από την εκκλησία των Αγίων Αναργύρων, σε μια τοποθεσία ονομαζόμενη "Κολώνες", υπήρχαν μέχρι το τέλος του 18ου αιώνα δύο όρθιες κολώνες από αρχαίο ναό. Ο σημερινός επισκέπτης του Παλαιόκαστρου σκοντάφτει διαρκώς σε πώρινους ογκόλιθους, μικρά κολωνάκια και άλλα διάφορα αρχιτεκτονικά κατάλοιπα του αρχαίου οικισμού, εντοιχισμένα σε πανέμορφους αγροτικούς οικίσκους που κτίστηκαν εκεί γύρω. Στην περιοχή υπάρχει επίσης αρχαίο πηγάδι με πώρινο στόμιο.

Ένας από τους περιηγητές που πέρασαν από τα Κύθηρα ο Nicobey διηγείται πως εκεί υπήρχε το άγαλμα της ωραίας Ελένης που μετά μεταφέρθηκε στην Βενετία. Διηγείται ακόμη πως υπήρχε μια παράδοση σύμφωνα με την οποία εδώ χάρηκε ο Πάρης τον έρωτά του με την Ελένη μετά την απαγωγή της. Ακόμη πως εκεί υπήρχε κάστρο του Μενελάου και ένας τετράγωνος πύργος.

Σύμφωνα με τον μύθο της γέννησης της Αφροδίτης, όταν ο Κρόνος έκοψε τα γεννητικά όργανα του Ουρανού, τα πέταξε στη θάλασσα. Καθώς τα κύματα έσπρωχναν τη ματωμένη σάρκα μία εδώ και μία εκεί, σχηματίστηκε ένας άσπρος αφρός γύρω της, που σιγά σιγά έπαιρνε μορφή γυναίκας. Όταν ο αφρός ταξιδεύοντας άραξε στην Κύπρο, στα ακρογιάλια της Πάφου, η γυναίκα βγήκε στη στεριά. Έτσι γεννήθηκε μια Θεά πανέμορφη, που την είπαν Αφροδίτη, επειδή είχε βγει από τον αφρό. Ειπώθηκε και Αναδυομένη, επειδή αναδύθηκε από τα κύματα και Κυπρίς ή Κυπρογένεια, επειδή στην Κύπρο πρωτοπάτησε το πόδι της στεριά, και Κυθέρεια, επειδή λέει ο αφρός, πριν αράξει στην Κύπρο, είχε περάσει μπροστά από τα Κύθηρα.