Δίπλα στον Βόρειο Οδικό Άξονα της Κρήτης (σε κοντινή απόσταση από το Ηράκλειο, μόλις 15χλμ) βρίσκονται τα απομεινάρια ενός παλιού φρουρίου που γίνονται ένα με τα χρώματα του βράχου στο ύψωμα που δεσπόζει πάνω από την παραλία του Παλαιόκαστρου.
Το φρούριο ανήκει στην περίφημη 14άδα κάστρων που έκτισαν οι Γενουάτες, με αρχηγό τον Enrico Pescatore, μετά το 1024, για να οχυρώσουν την Κρήτη. Το 1211, όμως, έχασαν την κυριαρχία του νησιού από τους Ενετούς και το εγκατέλειψαν. Οι Ενετοί, «θυμήθηκαν» το κάστρο το 1573, όταν οι Τούρκοι εξαπλώνονταν στην Μεσόγειο, κι έτσι το ανοικοδόμησαν.
Χτισμένο στην κορυφή του μεγάλου, ασβεστολιθικού βράχου το Παλαιόκαστρο (Castel Paleocastro) αποτελούσε αναγκαίο συμπληρωματικό έργο της μεγάλης Μεσαιωνικής οχύρωσης του Χάνδακα, που σε συνδυασμό με τα τείχη της πόλης που προστάτευσαν τον Χάνδακα για μεγάλο χρονικό διάστημα από τις επιδρομές των Οθωμανών, αλλά όταν η πόλη τελικά κατακτήθηκε (το 1669) οι Τούρκοι κατέστρεψαν μεγάλο τμήμα του.
Πιστεύεται ότι το φρούριο ήταν χτισμένο πάνω στα ερείπια αρχαίας ακρόπολης και σώζεται ένα αρκετά μεγάλο τμήμα του, κατασκευασμένο σε διαφορετικά επίπεδα λόγω του κεκλιμένου εδάφους, τα τείχη του φρουρίου είχαν κλίση προς τα μέσα, σύμφωνα με τις επιταγές της νέας οχυρωματικής τέχνης της εποχής, για να αντέχουν τις οβίδες. Η κεντρική του πύλη βρισκόταν στη νότια πλευρά του φρουρίου. Πρόκειται για μία πύλη μοναδικής αρχιτεκτονικής όπου η μισή είναι σκαλισμένη επάνω στον βράχο και η άλλη μισή είναι κτιστή. Βορειοανατολικά του φρουρίου, (και για να φαίνεται από απόσταση), είναι ενσωματωμένος επάνω στην κεντρική τοιχοποιία, ο φτερωτός λέοντας του Αγίου Μάρκου. Αντίστοιχο έμβλημα συναντάμε και στο κάστρο του Κούλε.
Τέλος, το φρούριο Παλαιοκάστρου, χαρτογραφήθηκε και μελετήθηκε για πρώτη φορά από τον G.Gerola, ο οποίος το φωτογράφισε και το αποτύπωσε στις αρχές του 20ου αιώνα.