By the Byzantine period, a tower known as Castellum Comunis stood on the site. In 1303, the tower was destroyed in an earthquake but was repaired.

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.

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

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.

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

The fortress is made up of two parts: a high rectangular section, and a slightly lower semi-elliptical section. Its walls are up to 8.7m thick at some places, and it has three entrances. The fort has two stories, with a total of 26 rooms, which were originally used as barracks, a prison, storage rooms, a water reservoir, a church, a mill and a bakery.

A lighthouse tower is located on the northern part of the fort.