Το Ηράκλειο με την εγκατάσταση των Ενετών στα 1211 εξελίχθηκε στο σπουδαιότερο κέντρο της πολιτικής, στρατιωτικής, πνευματικής και εμπορικής ζωής του Νησιού.Οι Ενετοί αρχικά αρκέστηκαν στην οχύρωση που βρήκαν όταν έφθασαν στο νησί, δηλαδή την υπάρχουσα αραβική – βυζαντινή, τμήματα της οποίας σώζονται ακόμη και σήμερα, πίσω από νέα κτίσματα, στην πορεία των οδών Χάνδακος, Δαιδάλου, Δουκός Μποφώρ και στο λιμάνι της πόλης. Επέφεραν όμως σʼ αυτήν κάποιες επιδιορθώσεις, προκειμένου να προστατευθούν από τις εσωτερικές αναταραχές που είχαν με το ντόπιο στοιχείο. Με τον καιρό διαπιστώνοντας ότι ο τουρκικός κίνδυνος γινόταν ολοένα και πιο ορατός και απειλητικός, άρχισαν το σχεδιασμό και την ανοικοδόμηση ενός νέου οχυρωματικού περιβόλου (αυτού που διασώζεται μέχρι σήμερα και περιβάλλει την παλιά πόλη) που θα περιελάμβανε την πόλη μαζί με τα προάστια που είχαν τότε δημιουργηθεί. Τα νέα τείχη σχεδίασαν διάφοροι μηχανικοί σταλμένοι από τη Βενετία, ο κυριότερος εκ των οποίων ήταν ο διασημότερος στρατιωτικός μηχανικός της Βενετίας, ο Michele Sanmicheli.

Ο σχεδιασμός και η κατασκευή της νέας οχύρωσης του Χάνδακα έγινε σε διάφορες φάσεις και κράτησε σχεδόν δύο αιώνες ξεκινώντας από τα μέσα περίπου του 15ου αιώνα. Ο σχεδιασμός έγινε με βάση τις νέες αρχές της οχυρωματικής τέχνης με την καθιέρωση του προμαχωνικού συστήματος και τις ανάγκες που προέκυψαν από την εφεύρεση της πυρίτιδας.

Ο νέος αμυντικός περίβολος, που έχει σχήμα τριγώνου με βάση στη θάλασσα, έχει περίμετρο περίπου 5 χιλιόμετρα. Την οχύρωση συμπλήρωνε, από την πλευρά του χερσαίου τμήματος, τάφρος και άλλα εξωτερικά οχυρά. Χαρακτηριστικό στοιχείο του οχυρωματικού σχεδιασμού αποτελούσαν οι προμαχώνες (Fronte Bastionato) που ήταν συνολικά επτά από ανατολικά προς τα δυτικά: ο Προμαχώνας Σαμπιονάρα (της Άμμου, που ανακατασκευάστηκε από τους Τούρκους), ο Προμαχώνας Βιτούρι, ο Προμαχώνας Ιησού, ο Προμαχώνας Μαρτινέγκο, ο Προμαχώνας Βηθλεέμ, ο Προμαχώνας Παντοκράτορα και ο Προμαχώνας Αγ. Ανδρέα (επίσης ανακατασκευασμένος από τους Τούρκους). Οι Προμαχώνες ενώνονταν μεταξύ τους με ευθύγραμμα τμήματα (cortina) και στα σημεία ένωσης σχηματίζονταν δύο χαμηλές πλατείες, χαμηλότερα από το επίπεδο του ίδιου του προμαχώνα και ψηλότερα από την τάφρο. Ένα άλλο χαρακτηριστικό στοιχείο του οχυρωματικού περιβόλου, που επιβλήθηκε, σε ορισμένες περιπτώσεις, για λόγους μεγαλύτερης ασφάλειας και προστασίας των αμυνομένων, εξαιτίας της ανομοιομορφίας του φυσικού εδάφους έξω από την τάφρο, ήταν η κατασκευή επιπρομαχώνων (cavalieri). Κατασκευάστηκαν τρεις μεγάλοι επιπρομαχώνες: ο επιπρομαχώνας Βιττούρι, ο επιπρομαχώνας Μαρτινέγκο και ο επιπτομαχώνας Τζάνε απέναντι από τον προμαχώνα Σαμπιονάρα.

Οι Τούρκοι τέλος, όταν κατέλαβαν τον Χάνδακα και ανακατασκεύασαν τον προμαχώνα του Αγίου Ανδρέα, πρόσθεσαν έναν επιπρομαχώνα.Το παραθαλάσσιο τμήμα των τειχών κατασκευάσθηκε και εδράστηκε πάνω στην υπάρχουσα βραχώδη ακτή. Προς την ανατολική πλευρά το τείχος κατέληγε στο μεγάλο φρούριο που προστάτευε το λιμάνι, το λεγόμενο Castello del Molo (Κούλε).