Palaiokastro fortress is a Venetian fortress built to protect the bay where was the capital city Candia alongside the fortress of Koules. Its construction begun in 1573 and completed in 1595 by the commander Latino Ortsini.

In the same place allegedly was the citadel of the ancient city Kytaion or the ancient city of Elea. The fortress is built on a Genoese castle of the 13th century. The fortress has triangular shape following the natural relief of the cliff on which it is built. Inside the fortress was created three uneven squares to exploit the steep cliff.

As seen from documents of that time and a map, the fortress had a garrison headquarters, barracks, church, watchtowers, tanks and weapons depots. The entrance was on the south side carved into the rock and lead to the lower square. In the northeast outer corner there was relief decoration which depicted the winged lion of St. Mark, the same that adorns the fortress of Koules. It also stated that the shot range of its seven cannons could reached Almiros river where was crossed by  those of the cannon of the city fortifications.

The fortress is located in the homonymous village Palaiokastro about 8 kilometers north of the city of Heraklion. The fort is not yet officially open to visitors but there are plans for its recovery conservation and enhancement as a visited monument.