Το φρούριο Παλαιόκαστρο κτίστηκε από τους Ενετούς στη θέση της αρχαίας πόλης Απτέρα, που ήταν φύσει οχυρή, για να προστατεύσουν το κόλπο της Σούδας από ενδεχόμενες επιθέσεις ή επιδρομές. Τα τείχη του, που είχαν προσανατολισμό από Βορρά προς Νότο σε μερικά σημεία είχαν πάχος 1.5μ, ύψος 3μ και ήταν εφοδιασμένο με θολωτές δεξαμενές. Ένας πλατύς δρόμος το συνέδεε με τη θάλασσα.
Κοντά στο φρούριο, όπως συνήθως, δημιουργήθηκε μικρός οικισμός (βούργος), όπου ο Ενετός Generale Giannbatista del Monte σχεδίαζε να μεταφέρει τους κατοίκους της πόλης των Χανίων, αφού πρώτα κατεδαφίσει το φρούριο και μωλώσει το λιμάνι τους, επειδή τη θεωρούσε ακατάλληλη για άμυνα. Κάτι τέτοιο όμως δεν έγινε ποτέ.
Όταν ο Μπαρμπαρόσα λεηλάτησε τα βόρεια παράλια της Κρήτης το 1538, κατέστρεψε το Παλαιόκαστρο και τον οικισμό του. Και το έργο της καταστροφής ολοκληρώθηκε από τον Σουλτάν Σελήμ, όταν επιτέθηκε κατά των Χανίων, κι έτσι σήμερα ελάχιστα απομένουν από το τότε φρούριο.
Με το Παλαιόκαστρο συνδέονται πολλά ιστορικά γεγονότα της επανάστασης του 1821. Ένα από αυτά είναι το εξής: Στις 30 Σεπτεμβρίου 1822 οι Αιγύπτιοι έκαναν απόβαση στην Αμφιμαλλικό Κόλπο (το σημερινό κόλπο της Γεωργιούπολης) με 3000 στρατιώτες και άρχισαν αμέσως εκκαθαριστικές επιχειρήσεις, κατά τις οποίες έσφαξαν και τους 12 φρουρούς του Παλαιόκαστρου.