Από τη Βυζαντινή περίοδο ο οικισμός του Ηρακλείου ονομαζόταν Κάστρο λόγω των τειχών που τον περιέβαλλαν. Το 824 μ. Χ. η Κρήτη καταλήφθηκε από τους Σαρακηνούς, οι οποίοι οχύρωσαν την πρωτεύουσα με τείχη φτιαγμένα από άψητους πλίνθους με τρίχες αιγών και χοίρων. Το τείχος ήταν αρκετά πλατύ και το περιέβαλλε βαθειά τάφρος, λόγω της οποίας το Ηράκλειο ονομαζόταν επί αιώνες «Φρούριο της Τάφρου». Το 961 η Κρήτη επανέρχεται στα χέρια των Βυζαντινών, οι οποίοι φτιάχνουν το φρούριο Ρόκκα στο Κανλί Καστέλι και ενισχύουν την οχύρωση γύρω από την πόλη του Ηρακλείου, κατασκευάζοντας κι άλλα οχυρωματικά έργα. Το 1206 η πόλη καταλαμβάνεται από τους Γενουάτες, οι οποίοι οχυρώνουν το φρούριο του Χάνδακα. Το 1217 η Κρήτη περνάει στα χέρια των Ενετών, οι οποίοι προσάρμοσαν και επισκεύασαν τα ήδη υπάρχοντα τείχη. Μετά το 1453 οι Ενετοί κτίζουν δεκάδες φρούρια στο νησί. Τα σημερινά τείχη του Ηρακλείου άρχισαν να κτίζονται το 1462 και η κατασκευή τους διήρκεσε περισσότερο από έναν αιώνα. Το τείχος είχε τριγωνικό σχήμα, έκταση 3 χλμ. και ήταν ένα απόρθητο κτίσμα, ενώ έξω από το κάστρο υπήρχαν και μικρότερα φρούρια. Το μεγάλο κάστρο καταλήφθηκε, μετά από 23ετή πολιορκία, από τους Τούρκους το 1669. Οι Τούρκοι επισκεύασαν και προσάρμοσαν τα τείχη στις ανάγκες τους, ενώ αλλάξουν τις ονομασίες. Το φρούριο του Ηρακλείου θεωρείται ένα από τα καλύτερα διατηρημένα ενετικά έργα στην Ευρώπη.