Η διαρκής κατοίκηση και οι αλλεπάλληλες φυσικές και ανθρώπινες καταστροφές σχεδόν εξαφάνισαν τα λείψανα της αρχαίας πόλης Ηράκλειον, που αναφέρεται από το Στράβωνα ως ένα από τα επίνεια της Κνωσού. Φαίνεται πάντως ότι το μικρό φυσικό λιμάνι αξιοποιήθηκε στο έπακρο, ίσως ήδη από τους μινωικούς χρόνους, καθώς διάσπαρτα ευρήματα από τους μινωικούς ως τους ρωμαϊκούς χρόνους έρχονται κατά καιρούς στο φως. Η πόλη στην ελληνιστική περίοδο υπήρξε ισχυρά οχυρωμένη και καταλάμβανε σημαντική έκταση. Στους ρωμαϊκούς χρόνους ήταν ένα από τα λίγα ασφαλή λιμάνια της βόρειας ακτής της Κρήτης. Μια πολυτελής ρωμαϊκή οικία, πλούσια κτερισμένες ταφές, διάσπαρτα ανάγλυφα, αρχιτεκτονικά μέλη σε δεύτερη χρήση καθώς και επιγραφές μαρτυρούν την ευμάρεια της πόλης κατά τη ρωμαϊκή περίοδο. Στους πρωτοβυζαντινούς χρόνους η πόλη έγινε έδρα επισκοπής, αναφερόμενη στα πρακτικά των Συνόδων αρχικά ως Heracleae (343 μ.Χ.) και αργότερα ως Ηρακλειούπολη (Ζ΄ Οικουμενική Σύνοδος, 787 μ.Χ.). Οι ανασκαφικές έρευνες έχουν φέρει μέχρι σήμερα στο φως ελάχιστα κτηριακά λείψανα της περιόδου αυτής, η σπουδαιότητα ωστόσο και η έκταση της πόλης τεκμηριώνεται από την αφθονία των κινητών ευρημάτων (αρχιτεκτονικά γλυπτά, κεραμική, νομίσματα, μικροαντικείμενα). Από τα μέσα του 7^ου αιώνα (654 μ.Χ.) η πόλη άρχισε να αισθάνεται την απειλή της αραβικής παρουσίας στη θάλασσα του Αιγαίου. Σε μια προσπάθεια αποτροπής της καταστροφής οι Βυζαντινοί αποφάσισαν να την οχυρώσουν εκ νέου, αξιοποιώντας τα λείψανα της ελληνιστικής της οχύρωσης, όπως έπραξαν για ένα δίκτυο άλλων σημαντικών πόλεων του νησιού. Η ισχυρή οχύρωση με τους τετράγωνους πύργους και την τάφρο, που οδήγησε τους Άραβες να ονομάσουν το Ηράκλειο Rabdh el Khandaq, το Φρούριο της Τάφρου, δεν στάθηκε ικανή ωστόσο να την προστατεύσει. Οι Άραβες αποβιβάστηκαν στη νότια Κρήτη, πιθανόν στον Κερατόκαμπο, το 822/3 και την κατέκτησαν σταδιακά ως το 828. Τελευταία έπεσε στα χέρια τους η πόλη του Ηρακλείου, η οποία αποτέλεσε το κύριο ορμητήριο των επιδρομών αλλά και του εμπορίου τους στη Μεσόγειο. Μια πληθώρα χάλκινων αραβικών νομισμάτων και κεραμική υψηλής ποιότητας με επιρροές από την Ανατολή και τη Δύση (Ισπανία) αποτελούν αδιάψευστο μάρτυρα για τα 150 χρόνια αραβικής κατοχής που άφησαν ανεξίτηλη τη σφραγίδα τους στο όνομα της πόλης. Το Khandaq έγινε από τους Βυζαντινούς Χάνδακας και από τους Βενετούς Candia.

Η απώλεια της Κρήτης υπήρξε ισχυρό πλήγμα για τη βυζαντινή επικυριαρχία στη Μεσόγειο. Η ανάκτησή της ωστόσο αποδείχθηκε πολύ δύσκολη υπόθεση. Μετά από αλλεπάλληλες αποτυχίες, το 961 μ.Χ., ο βυζαντινός στρατηγός και μετέπειτα αυτοκράτορας Νικηφόρος Φωκάς κατάφερε, υποσκάπτοντας τα τείχη, να την ανακαταλάβει.Ο Χάνδακας άρχισε σταδιακά ν’ ανακάμπτει και ως τα τέλη του 12^ου αι. γνώρισε μεγάλη εμπορική και οικονομική ανάπτυξη. Ωστόσο, πριν ακόμη από την Άλωση της Κωνσταντινούπολης από τους Φράγκους το 1204, ο έκπτωτος βυζαντινός αυτοκράτορας Ισαάκιος Β΄ παραχώρησε την Κρήτη στο Βονιφάτιο Μομφερατικό, ως αντάλλαγμα για τη συνδρομή του στην επανενθρόνισή του και αυτός με τη σειρά του εκχώρησε το νησί τους Βενετούς. Μετά από σύντομη κατάληψη από τους Γενουάτες πειρατές του Enrico Pescatore, η πόλη πέρασε τελικά στα χέρια των Βενετών το 1211 και η Candia αποτέλεσε έκτοτε την πρωτεύουσα του ενετικού Βασιλείου της Κρήτης, τον κυριότερο εμπορευματικό σταθμό της Βενετίας στην Ανατολική Μεσόγειο, στην οποία άνθισαν τα γράμματα και οι τέχνες. Με την κατάληψη της Κύπρου από τους Οθωμανούς το 1571, ο εμπορικός ρόλος της Candia ισχυροποιήθηκε. Οι Βενετοί προσπάθησαν να την προστατεύσουν μ’ ένα τεράστιο οχυρωματικό έργο, η επιβλητικότητα του οποίου αντανακλάται στο τελευταίο όνομά της (Μεγάλο Κάστρο). Όμως μετά από 21 ολόκληρα χρόνια σκληρής πολιορκίας και υπεράνθρωπης αντίστασης, που έμεινε γνωστή ως «Κρητικός Πόλεμος», ο τελευταίος υπερασπιστής της Francesco Morosini υποχρεώθηκε το 1669 να την παραδώσει στις δυνάμεις του Σουλτάνου.