Στην πραγματικότητα υπήρχαν δύο κτίσματα, ο σημερινός Κούλες που δεσπόζει στην άκρη του λιμανιού του Ηρακλείου κι ένας μικρότερος, ακριβώς απέναντι του, ο οποίος γκρεμίστηκε στις αρχές του 20^ου αιώνα για τη βελτίωση της λειτουργίας του λιμανιού. Το μικρό φρούριο κτίστηκε πρώτο από τους Ενετούς, για την καλύτερη οχύρωση του Χάνδακα, και ονομάστηκε Rocca al Mare (Φρούριο στη Θάλασσα). Μετά την ανακάλυψη της πυρίτιδας οι Ενετοί αποφάσισαν τη δημιουργία ενός μεγαλύτερου κτηρίου, που θα ικανοποιούσε καλύτερα τις ανάγκες τους. Έτσι κτίζεται το σημερινό φρούριο, η κατασκευή του οποίου ολοκληρώθηκε το 1540. Το κτήριο ήταν διώροφο, με 26 αίθουσες για διάφορες χρήσεις, ακόμα και φυλακές. Η μετονομασία του σε «Κούλες» έγινε από τους Τούρκους, οι οποίοι κατέλαβαν τη νήσο το 1669 και συνέχισαν την κατασκευή του. Σήμερα διατηρείται σε πολύ καλή κατάσταση και χρησιμοποιείται για πολιτιστικές εκδηλώσεις.