Η σημερινή πόλη του Ηρακλείου, σύμφωνα με τον Στράβωνα, βρίσκεται στη θέση που υπήρχε ένα από τα λιμάνια της Κνωσού με το όνομα Ηράκλεια. Το όνομα διατηρήθηκε στα Ρωμαϊκά και Βυζαντινά χρόνια. Το 824 Άραβες κατέλαβαν το νησί, έτσι οχυρώθηκε με τείχη και γύρω από αυτά μια μεγάλη τάφρο που ονομαζόταν Χάνδαξ (khandak = τάφρος). Οι Άραβες είχαν τον Χάνδακα σαν ορμητήριο και στην πόλη υπήρχε το μεγαλύτερο σκλαβοπάζαρο της ανατολικής Μεσογείου. Ο Νικηφόρος Φωκάς μετά από έξι εκστρατείες καταλαμβάνει το 961 την πόλη και σταματά την λεηλασία των Αράβων που ήταν μάστιγα όλης της Μεσογείου.

Κατά την Ενετοκρατία 1204 – 1669 η πόλη ονομάστηκε Candia (=κάστρο) που επικράτησε για όλο το νησί. Την περίοδο αυτή η πόλη γίνεται πρωτεύουσα του νομού και χτίζονται τα περίφημα Ενετικά τείχη. Η ανακατασκευή των τειχών άρχισε το 1462 και κράτησε 100 χρόνια. Τα σχέδια ήταν του μηχανικού Σανμικέλι και ήταν το τελειότερο δείγμα οχυρωματικών έργων. Εκτός από τα τείχη οι Ενετοί έκτισαν στην πόλη πολλά μεγαλόπρεπα κτίρια, κρήνες, υδραγωγεία κ.α. Την περίοδο αυτή υπήρχε και πολιτιστική άνθηση επηρεασμένη από την αναγέννηση, ιδιαίτερα μετά από την άλωση της Κωνσταντινούπολης όπου πολλοί λόγιοι και καλλιτέχνες κατέφυγαν εδώ. Τότε ιδρύθηκε η Σιναϊτική Σχολή της Αγίας Αικατερίνης όπου διδάσκονταν θεολογία, φιλοσοφία, νομική κ.α.

Μετά από 21 χρόνια πολιορκίας (1648 – 1669) οι Τούρκοι κατέλαβαν το φρούριο, ενώ για ολόκληρη την Κρήτη χρειάστηκαν 2 χρόνια. Επί Τουρκοκρατία η πόλη παρήκμασε και βυθίστηκε στο σκοτάδι. Η όψη της πόλης άλλαξε αφού πολλά κτίρια καταστράφηκαν και πολλές εκκλησίες μετατράπηκαν σε τζαμιά. Πολλοί ήταν οι Έλληνες που σκοτώθηκαν αλλά δεν έπαψαν να επαναστατούν μέχρι την μέρα που ελευθερώθηκαν. Μετά την Τουρκοκρατία η πόλη πήρε το παλιό της όνομα από την Επιτροπή Αγωνιστών που συνήλθε στους Αρμένους. Το 1913 ενώθηκε με το ελεύθερο Ελληνικό κράτος.
Κατά την περίοδο της Γερμανικής κατοχής οι κάτοικοι της πόλης αντιστάθηκαν θαρραλέα στον κατακτητή