Crete has always been and is still located at the crossroads of ancient sea-ways of the Mediterranean. The general area around the port of Heraklion, from the mouth of the River Kairatos (Katsambas) to the bay of “Dermatas”, has always been at the center of conflict between various peoples and civilizations. The entrance of the ancient Greek and Venetian port is dominated by the impressive Fortress of the Sea, Rocca al Mare or Castello al Mare, later named Koules. It was built in the 16th c., in the place of a Hellenistic-Byzantine tower, in order to protect the commercial port of strategic importance and the imposing fortified enceinte around Chandax (Heraklion) from the impending Οttoman menace. Its construction, which lasted for 17 years, required enormous amounts of money. The fact, however, that magnifies its historical value is that its building materials have carried the city’s memories through the centuries, form the time it served as a seaport for Minoan Cnossos to the Hellenistic Heraklion, the Venetian Candia and the Ottoman Megalo Kastro (“Great Fort”). This presentation unravels the history of the sea fort’s structural materials and seeks both their origin and their history. The islet of Dia, across the bay of Heraklion, was the source of the necessary raw materials used in the construction of the foundation islet of the sea fort, possibly in two separate historical eras. The materials used for the construction of the fort itself were, to a large extent, used for the second (or third) time and had been removed from already existing structures in nearby areas.