Héraklion a été particulièrement marquée par les conflits qui frappèrent la mer Méditerranée dans son ensemble, et plus particulièrement, son bassin oriental au cours du Moyen Âge et de l'époque moderne. Successivement aux mains des Byzantins, des Arabes, à nouveau des Byzantins, des Vénitiens, et des Ottomans, la forteresse de Koules est la représentation même de ces différentes influences sur l'île de Crète.
Selon les archéologues, le Koules a été bâti sur un ancien emplacement fortifié, peut-être arabe, entre le IXe et le Xe siècle. Les Arabes l'auraient donc construit après 825, date de leur conquête de la Crète. En effet, Al-Hakam Ier, émir de Cordoue, était en guerre contre les chrétiens d'Espagne. Subissant des défaites, des seigneurs qui lui été soumis se soulevèrent mais la prise de Barcelone en 803, lui donna l'occasion de chasser de nombreux rebelles de l'émirat. Ceux-ci, après plusieurs années d'exil, firent de la Crète un lieu de piraterie et de pillage avant de s'y installer pour lancer leurs assauts sur les côtes égéennes. Ils fondèrent alors la cité de El Khandak (l'actuelle Héraklion) et la fortifièrent légèrement, creusant un fossé le long de la ville, lui donnant son nom, et érigeant deux tours de défenses à l'entrée de la cité portuaire.
Les Byzantins, qui avaient longtemps contrôlé l'île, la reprirent vers 961-962, sous le commandement de Nicéphore Phocas. Ils bâtirent un Castellum Comunis, sur l'emplacement actuel de la forteresse. Il s'agissait d'une tour en pierre dont il ne reste plus rien aujourd'hui si ce ne sont des témoignages perpétués et recueillis par les auteurs italiens du XIVe siècle.
Avant, pendant, et après les Croisades, la République de Venise, à l'instar des Génois, s'occupa à étendre son emprise commerciale, quitte à conquérir des territoires pour s'en faire des comptoirs. La Crète tomba ainsi dans le giron vénitien. Lors de la Quatrième croisade, une lutte éclata entre les villes italiennes de Gênes, Pise et la République de Venise. Finalement, Venise en sortit vainqueur. La tour byzantine, encore en place, fut certainement aménagée aux besoins des soldats de Venise au début du XIIIe siècle. On ne sait pas précisément quand les Vénitiens lui destinèrent un rôle mais la plus vieille documentation à son sujet est une description de la tour dans les travaux du moine florentin Cristoforo Buondelmonti, datant de 1417.
Très rapidement, des forteresses furent construites, dans de nombreuses possessions vénitiennes contre de possibles attaques des musulmans ou de Byzantins. Chronologiquement, la première fortification vénitienne portuaire à Héraklion fut construite après 1208-1209, dates auxquelles correspond la conquête définitive de la Crète par Venise.
La forteresse de Koules n'était donc, dans un premier temps, qu'une tour rénovée pour servir au stockage de nourriture et de baraquements aux troupes installées à Héraklion. Mais un tremblement de terre la détruisit en 1303. Elle fut alors reconstruite par des architectes génois. Ce n'est qu'en 1462, que le sénat de la République de Venise s'attacha à bâtir une forteresse digne de ce nom à l'entrée du port d'Héraklion. Un autre tremblement de terre, en 1500 mit à terre l'édifice la forteresse. Finalement, la République de Venise fit appel à Michele Sanmicheli, issu des meilleurs architectes italiens du début du XVIe siècle. Le doge lui confia de fortifier comme il se devait la plupart des comptoirs vénitiens. Sanmicheli, même si nous ne sommes pas sûr de son travail sur la forteresse de Koules, en a surement conçu les plans puisque les murailles de la ville et l'érection de la forteresse, entre 1523 et 1540, correspondent à son travail en Crète, et en particulier à Candie (nom donné dès 1220 à Héraklion). C'est donc en dix sept années que furent dressées les impressionnantes défenses de Candie, alors surnommée par les Vénitiens, Megalo Castro, «la grande forteresse», et dont la partie principale était la forteresse Rocca al mare, devait avoir la forme que nous lui connaissons aujourd'hui.
Entre temps, la géopolitique avait changé en mer Égée. Les Byzantins s'étaient effacés, Rhodes était tombée et un empire était né, celui des Ottomans. La forteresse de Koules allait alors jouer son rôle principal durant le siège de Candie, qui allait durer vingt et un ans, de 1648 à 1669. Les Ottomans avaient déjà pris le reste de la Crète avant 1650. Pourtant, les lignes de fortifications (qui défendirent la ville portuaire d'attaques terrestres) et la forteresse (qui bloqua les assauts maritimes) allaient résister aux Turcs, prouvant l'efficacité des inventions de Michele Sanmicheli. Toute l'Europe chrétienne se précipite en Crète pour éviter une nouvelle conquête ottomane mais le siège est trop long. Le 16 septembre 1669, les assiégés acceptent les conditions turques. Malgré cette reddition, la ville ne s'est pas rendue et les fortifications jouèrent largement le rôle prévu par les doges.
Les Ottomans s'installèrent donc à Candie (Héraklion). Ceux-ci transforment la forteresse en prison et renforcent les murailles de Sanmicheli. Elle prit alors son nom actuel, Koules. Il est dit que la plupart des héros locaux, révoltés contre les Ottomans, furent emprisonnés là et y seraient morts. Pour s'assurer d'une meilleure défense, les Ottomans construisirent une autre structure, sur la berge opposée au Koules. Ce «Petit Koules» ne nous est malheureusement pas parvenu. En 1936, l'agrandissement de la ville, durant les premiers mois de la dictature de la junte de Ioánnis Metaxás, se fit par la démolition de cette petite fortification ainsi que d'une partie des murs d'enceinte construits par les vénitiens.