Το φρούριο του Παλαιοκάστρου αποτελεί Ενετικό οχυρωματικό κτίσμα για την προστασία του κόλπου όπου βρισκόταν η πρωτεύουσα Candia παράλληλα με το φρούριο του Κούλε. Ξεκίνησε να χτίζεται το 1573 και ολοκληρώθηκε το 1595 από τον αρχιστράτηγο Λατίνο Ορτσίνι.
Στην ίδια θέση εικάζεται ότι υπήρχε η ακρόπολη της αρχαίας πόλης Κύταιον ή η αρχαία πόλη Ελαία. Σίγουρα όπως φαίνεται από αναφορές το φρούριο είναι κτισμένο πάνω σε γενοβέζικο κάστρο του 13ου αιώνα. Το φρούριο έχει τριγωνική μορφή ακολουθώντας το φυσικό ανάγλυφο του βράχου πάνω στον οποίο είναι κτισμένο. Στο εσωτερικό του φρουρίου έχουν δημιουργηθεί τρεις ανισόπεδες πλατείες για την εκμετάλλευση της απότομης κλίσης του βράχου.
Όπως φαίνεται από έγραφα της εποχής με χάρτη, το φρούριο διέθετε φρουραρχείο, στρατώνες, εκκλησία, σκοπιές, δεξαμενές και αποθήκες όπλων. Η είσοδος του βρισκόταν στην νότια πλευρά σκαλισμένη στο βράχο και οδηγούσε στην κατώτερη πλατεία. Στην βορειοανατολική εξωτερική γωνία υπήρχε ανάγλυφη διακόσμηση η οποία παρίστανε τον φτερωτό λέοντα του Αγίου Μάρκου, τον ίδιο που κοσμεί και το φρούριο του Κούλε. Επίσης αναφέρεται ότι η βολή των 7 κανονιών που διέθετε έφτανε μέχρι τον αλμυρό ποταμό όπου διασταυρωνόταν με αυτά των κανονιών των οχυρώσεων της πόλης.
Το φρούριο βρίσκεται στον ομώνυμο οικισμό Παλαιοκάστρου 8 περίπου χιλιόμετρα βόρεια από την πόλη του Ηρακλείου. Το φρούριο δεν είναι επίσημα επισκέψιμο όμως βρίσκεται στα σχέδια αποκατάστασης, συντήρησης και ανάδειξης του ως επισκέψιμο μνημείο.