Koules beneška trdnjava dominira vhod v staro pristanišče Heraklion. Benečani so jo imenovali "Rocca al Mare» (Sea trdnjava), danes pa je znano po svoji turški imenom "koules" (su Kulesi). To je eden izmed najbolj znanih in priljubljenih znamenitosti, je njen simbol.

Natančen izvor zgodovine trdnjave ni znana, vendar je pristanišče s strateškim položajem v Sredozemlju ni mogel ostati nezaščiteni. Prvi Grad je bil verjetno zgrajen na mestu Kulesa še v arabskem obdobju (9-10 stoletje). Nekateri viri so omenili trdnjavo v bizantinskem obdobju (10-13 stoletij). Obstajajo skice potnikom v času, za katerega prej so skic trdnjave menih Buondelmonti (1429).

V sredini 14. stoletja v Evropi je bil smodnik (mešanica Salitra, žveplo in ogljik). Njegov nastop je igral pomembno vlogo v vojni in radikalno spremenil vojaške znanosti. Treba je revidirati obrambo nekdanjih utrdb. Tako je do sredine 15. stoletja je bil sedanji grad šibka in neuporabna za obrambo mesta objekta. Leta 1462 je beneški senat odobril ambiciozen program za krepitev Heraklion in bližnjih območij. V okviru tega projekta, je bila stara utrdba pristanišča, ki jih nato v potresu in rušilno močjo morja temeljito prizadela, porušili (1523), in na njenem mestu zgradili novo stavbo, ki je preživela tudi ta dan. Dela so trajala do leta 1540.

Trdnjava je bila zgrajena na platformi, ki ga tvorijo naravne skalne police. Stavba ima dve nadstropji z 26 sobami in pokriva površino 3.600 m² Debelina zunanjih sten skoraj 9 metrov, notranje stene ponekod visok kot 3 metre. Obstajajo trije vhodi v gradu od zahoda (glavni vhod), severnih in jugozahodnih straneh. Zunanje stene so bile okrašene z različnimi znaki, napisi in grbi. Vhod je okrašena z marmorja reliefi upodobljen krilati lev sv Marka (simbol Beneške republike). Dva od teh olajšav so preživeli.

V pritličju se nahaja zapor in prostorov, kjer so shranjene zaloge hrane in streliva. Tam so bili tudi ločeni prostori za vojake, častnike in guvernerja. Trdnjava je imel mlin, peč in kapelo, ki jo zagotavlja avtonomijo. Na severni strani v zgornjem nadstropju je svetilnik. Se je v času vladavine Turkov zaključili zgornjo raven trdnjave, je dodal vrzeli, prostor za pištole in majhno mošejo.

Danes je utrdba koules včasih uporablja za likovne razstave, ki so v sobi v prvem nadstropju. V zgornjem nadstropju gosti koncertov in predstav, če vreme dopušča.