Ο όρμος της πόλης του Ηρακλείου φαίνεται ότι είχε διαμορφωθεί σε λιμάνι, και μάλιστα οχυρωμένο, ήδη από την ελληνιστική περίοδο. Προστατευόταν από ένα προσήνεμο λιμενοβραχίονα στα βορειοδυτικά και ένα υπήνεμο στα νότια. Στην ανατολική απόληξη του προσήνεμου λιμενοβραχίονα πρέπει να υπήρχε ένας πύργος – φάρος, που πιθανότατα ανακατασκευάστηκε, όπως και η υπόλοιπη οχύρωση της πόλης, στον 7^ο ή 8^ο αι. μ.Χ., υπό την απειλή των αραβικών επιδρομών. Πιθανότατα πρόκειται για τον ίδιο πύργο που οι Βενετοί ονόμασαν Castellum Communis και μετασκεύασαν ελαφρά, διευρύνοντας τη στέψη του κατά τα δυτικά πρότυπα, όπως απεικονίζεται στο σχέδιο του Christoforo Buondelmonti του 1415. Ένας μικρότερος πύργος, που απεικονίζεται σε γκραβούρες του 15^ου αιώνα στο άκρο του υπήνεμου λιμενοβραχίονα, ίσως συμπλήρωνε την προστασία της εισόδου του λιμένα, τουλάχιστον κατά τη Βενετοκρατία. Το Castellum Communis επλήγη σοβαρά από το σεισμό του 1508 και το 1523 αποφασίστηκε να κατεδαφιστεί προκειμένου στη θέση του ν΄ ανεγερθεί ένα φρούριο προσαρμοσμένο στις αρχές του προμαχωνικού συστήματος (fronte bastionato), στα πλαίσια σχεδιασμού της νέας αμυντικής ζώνης της πόλης που είχε αποφασιστεί ήδη από το 1462. Αντίστοιχα φαίνεται να ανακατασκευάστηκε το μικρό φρούριο στο άκρο του υπήνεμου λιμενοβραχίονα, που απεικονίζεται στην ξύλινη μακέτα του λιμένα του έτους 1614 στο Museo Storico Navale της Βενετίας και κατεδαφίστηκε το 1936.

Οι εργασίες κατασκευής άρχισαν πριν το 1525. Για την οικοδόμηση του νέου φρουρίου, που θα είχε αρκετά μεγαλύτερες διαστάσεις, χρειάστηκε να διευρυνθεί τεχνητά η κρηπίδα έδρασης. Για την κατασκευή της ποντίστηκαν παλιά πλοία φορτωμένα με βράχους και ογκόλιθους που μεταφέρθηκαν από τη Ντία και τα Φρασκιά στον κόλπο του Παλαιοκάστρου. Για την προστασία του φρουρίου δημιουργήθηκε στη βόρεια πλευρά ένας μικρός ισχυρός μόλος με ημικυκλική απόληξη (sperone) που διέθετε δέστρες για τα πλοία. Στη ΒΔ πλευρά δημιουργήθηκε ένας κυματοθραύστης (porporella). Η νέα κατασκευή ονομάστηκε Castello a Mare (φρούριο στη θάλασσα) ή Rocca a Mare (βράχος στη θάλασσα). Για την κατασκευή του φρουρίου χρησιμοποιήθηκαν λαξευτοί ασβεστόλιθοι που σε μεγάλο ποσοστό φαίνεται να προήλθαν από την οχύρωση των ελληνιστικών χρόνων και τα λατομεία της ευρύτερης περιοχής. Η κατασκευή είχε ολοκληρωθεί ως το 1540, ωστόσο υπέφερε διαρκώς από την καταστροφική μανία των κυμάτων, που ανάγκαζε τους Βενετούς να πραγματοποιούν διαδοχικές επισκευές. Οι δυσκολίες και τα προβλήματα, αλλά και οι προτάσεις για τροποποιήσεις στην κατασκευή συνεχίστηκαν ως την έναρξη της πολιορκίας του Χάνδακα, ενώ στη διάρκειά της ο αμυντικός ρόλος του φρουρίου εξουδετερώθηκε γρήγορα από τους πολιορκητές. Μετά την άλωση του Χάνδακα το 1669, οι Οθωμανοί πραγματοποίησαν επεμβάσεις στο κτίσμα, το οποίο αποκαλούσαν στο εξής Φρούριο του Νερού (Su Kulesi), ονομασία που διατήρησε στα νεότερα χρόνια (Κούλες). Η νότια πλευρά, που είχε καταρρεύσει από τις βολές των κανονιών, επισκευάστηκε και πάνω από το ευθύγραμμο βενετσιάνικο στηθαίο κατασκευάστηκε άλλο με κανονιοθυρίδες και επάλξεις, με ταυτόχρονη υπερύψωση του περιμετρικού διαδρόμου κίνησης. Στη νότια πλευρά του δώματος κατασκευάστηκε τέμενος με μιναρέ. Το 1864 ο βενετσιάνικος φάρος επισκευάστηκε από τη Γαλλική Εταιρία Οθωμανικών Φάρων. Αρκετές επισκευές στο φρούριο πραγματοποιήθηκαν τόσο την περίοδο της Κρητικής Πολιτείας όσο και μετά την ένωση της Κρήτης με την Ελλάδα το 1913.