Η ιστορία του κάστρου ξεκίνησε τον Μεσαίωνα, όταν ένα παρεκκλήσιο αφιερωμένο στην Παναγία της Πένα κτίστηκε στην κορυφή του λόφου, επάνω από τη Σίντρα. Σύμφωνα με την παράδοση, η κατασκευή έγινε μετά την εμφάνιση της Παναγίας.

Το 1493 ο βασιλιάς Ιωάννης Β΄, συνοδευόμενος από τη σύζυγό του βασίλισσα Ελεονόρα, έκανε ένα προσκύνημα στην τοποθεσία για να εκπληρώσει έναν όρκο. Ο διάδοχός του, ο βασιλιάς Εμμανουήλ Α΄, αγαπούσε επίσης πολύ αυτό το ιερό και διέταξε την ανέγερση ενός μοναστηριού σε αυτήν την τοποθεσία, το οποίο δωρήθηκε στο Τάγμα του Αγίου Ιερώνυμου . Για αιώνες η Πένα ήταν ένα μικρό, ήσυχο μέρος για διαλογισμό, όπου στεγάζονταν το πολύ δεκαοκτώ μοναχοί.

Τον 18ο αι. η μονή υπέστη σοβαρές ζημιές από κεραυνό. Ωστόσο, ήταν ο μεγάλος σεισμός της Λισαβόνας του 1755 που συνέβη λίγο αργότερα, ο οποίος επέφερε το μεγαλύτερο πλήγμα στο μοναστήρι, με αποτέλεσμα να γίνει ερείπια. Ωστόσο, το παρεκκλήσιο (και τα έργα του από μάρμαρο και αλάβαστρο που αποδίδονται στον Νικολάου Σαντερένε) σώθηκε χωρίς σημαντικές ζημιές.

Για πολλές δεκαετίες τα ερείπια παρέμειναν ανέγγιχτα, αλλά εξακολουθούσαν να εκπλήσσουν τον νεαρό πρίγκιπα Φερδινάνδο. Το 1838, ως βασιλικός σύζυγος Φερδινάνδος Β', αποφάσισε να αποκτήσει το παλαιό μοναστήρι, όλα τα γύρω εδάφη, το κοντινό κάστρο των Μαυριτανών και μερικά άλλα κτήματα στην περιοχή. Στη συνέχεια, ο βασιλιάς Φερδινάνδος Β΄ ξεκίνησε να μεταμορφώσει τα ερείπια του μοναστηριού σε ένα παλάτι, που θα χρησίμευε ως θερινή κατοικία για την πορτογαλική βασιλική οικογένεια. Η ανάθεση για την ανοικοδόμηση σε ρομαντικού στυλ δόθηκε στον αντιστράτηγο και μηχανικό ορυχείων Βίλχελμ Λούντβιχ φον Έσβεγκε. Ο Έσβεγκε, ένας Γερμανός ερασιτέχνης αρχιτέκτονας, είχε ταξιδεύσει πολύ και πιθανότατα γνώριζε πολλά κάστρα κατά μήκος του ποταμού Ρήνου. Η κατασκευή πραγματοποιήθηκε μεταξύ 1842 και 1854, αν και σχεδόν ολοκληρώθηκε το 1847: ο βασιλιάς Φερδινάνδος Β΄ και η βασίλισσα Μαρία Β΄ παρενέβησαν αποφασιστικά σε θέματα διακόσμησης και συμβολισμού . Μεταξύ άλλων, ο βασιλιάς πρότεινε να συμπεριληφθούν αψίδες, μεσαιωνικά και ισλαμικά στοιχεία, και σχεδίασε επίσης ένα περίτεχνο παράθυρο για την κύρια πρόσοψη (εμπνευσμένο από το παράθυρο του συλλόγου της μονής του Τάγματος του Χριστού στο Tόμαρ).

Μετά το τέλος του Φερδινάνδου Β΄ το παλάτι πέρασε στην κατοχή της δεύτερης συζύγου του Ελίζας Χένσλερ, κόμισσας της Έντλα. Στη συνέχεια, η τελευταία πώλησε το παλάτι στον Λουδοβίκο Α΄, ο οποίος ήθελε να το ανακτήσει για τη βασιλική οικογένεια, και στη συνέχεια το παλάτι χρησιμοποιήθηκε συχνά από την οικογένεια. Το 1889 αγοράστηκε από το πορτογαλικό κράτος και μετά τη Ρεπουμπλικανική Επανάσταση του 1910 χαρακτηρίστηκε ως εθνικό μνημείο και μετατράπηκε σε μουσείο. Η τελευταία βασίλισσα της Πορτογαλίας, η Αμαλία σύζυγος του Καρόλου Α΄, πέρασε το τελευταίο της βράδυ στο παλάτι, πριν φύγει από τη χώρα στην εξορία.

Το παλάτι προσέλκυσε γρήγορα επισκέπτες και έγινε ένα από τα πιο δημοφιλή μνημεία της Πορτογαλίας. Με την πάροδο του χρόνου τα χρώματα των κόκκινων και κίτρινων προσόψεων ξεθώριασαν και για πολλά χρόνια το παλάτι προσδιοριζόταν οπτικά ως εντελώς γκρι. Στα τέλη του 20ου αι. το παλάτι ξαναβάφττηκε και τα αρχικά χρώματα αποκαταστάθηκαν.

Το 1995 το παλάτι και το υπόλοιπο πολιτιστικό τοπίο της Σίντρα χαρακτηρίστηκαν ως Μνημεία Παγκόσμιας Κληρονομιάς από την UNESCO.