Posiblemente el emirato de Creta fue el que fortificó el lugar por primera vez, hacia el siglo IX o X. En el segundo período bizantino, en el lugar se encontraba una torre conocida como Castellum Comunis,[1]​ que un terremoto destruyó en 1303 —y fue posteriormente reparada—.[2]​

 El León de San Marcos en uno de los muros de la fortaleza, símbolo de la república veneciana.

Con la llegada de la República de Venecia a la isla, en 1462 su Senado aprobó un programa para mejorar las fortificaciones de Candía (la actual Heraclión). Finalmente, la torre bizantina fue demolida en 1523 y en su lugar se comenzó a construir el Castello a Mare, que se completó en 1540. Para las obras de esta fortaleza los barcos antiguos se llenaban de piedra y hundían para formar un rompeolas, para así aumentar el área de la plataforma sobre la que se levantó el edificio.[1]​ En 1630, el fuerte estaba armado con dieciocho cañones en la planta baja y veinticindo en el camino que conducía al techo.[2]​

Durante el asedio de Candía, que duró veintiún años, las baterías otomanas neutralizaron fácilmente la potencia de fuego del fuerte. Los invasores finalmente tomaron la fortaleza en 1669, después de que los venecianos entregaran toda la ciudad. No hicieron grandes modificaciones a la estructura, salvo la adición de algunas almenas y troneras. Construyeron un pequeño fuerte conocido como Pequeño Koules en el lado terrestre, pero fue demolido en 1936 mientras se urbanizaba el núcleo de la población.[1]​ En la actualidad, el edificio se conserva restaurado y abierto al público.[2]​

↑ a b c «The Venetian Castello a Mare in Heraklion». Explore Crete (en inglés). Archivado desde el original el 6 de abril de 2015. Consultado el 20 de septiembre de 2023.  ↑ a b c «Koules Fortress». Heraklion Crete (en inglés). Consultado el 20 de septiembre de 2023.