The site was possibly first fortified by the Arabs in the 9th or 10th centuries. By the second Byzantine period, a tower known as Castellum Comunis stood on the site.[1] In 1303, the tower was destroyed in an earthquake but was repaired.[2]

In 1462, the Venetian Senate approved a programme to improve the fortifications of Candia. Eventually, the Byzantine tower was demolished in 1523, and the Castello a Mare began to be built instead. Old ships were filled with stone, and were sunk to form a breakwater and increase the area of the platform on which the fortress was built. The fortress was completed in 1540.[1]

In 1630, the fort was armed with 18 cannons on the ground floor, and 25 cannons on the pathway leading to the roof.[2]

During the 21-year long Siege of Candia, Ottoman batteries easily neutralized the fort's firepower. The Ottomans eventually took the fort in 1669, after the Venetians surrendered the entire city. They did not make any major alterations to the fort, except for the additions of some battlements and embrasures. They built a small fort known as Little Koules on the landward side, but this was demolished in 1936 while the city was being "modernized".[1]

The fortress has been restored, and it is now open to the public.[2] Art exhibitions and cultural activities are occasionally held at the fort.[1]