The Venetian barons of Chania asked Venice to build a fortress in Sfakia, for their protection from the pirates and the rebellions of the native people.
The Senate, however, was unwilling to do this, as the cost was too high. In 1371 the construction of the fortress began and it was completed in 1374. Meanwhile the local people tried to prevent its completion, destroying in the night what had been built during the day. The name Frangokastello (the castle of the Franks, that is, the Catholics) was given to the new fortress, echoing the contempt of the local people towards the conquerors.
In its present-day form, Frangokastello is not different from its pictures in the Venetian designs. It follows old fortification concepts,
" before the prevalence of the bastions system", which arrived in Crete before the middle of the 16th century. It is a rectangular building with vertical walls and four-sided towers at its 4 corners, of which the north-western one is the biggest. The towers and the walls end in jagged embrasures. The main entrance was in the south. However, in its present-day form it is a reconstruction from the 19th century. Over this entrance, the blazons of 4 eminent Venetian families were walled up. Two of them are still preserved, of the families Querini and Dolfin. Over the blazons there is the lion of St Marcus. One more entrance exists in the east. The three small towers are preserved (with several reconstruction stages mainly in the upper floors). From the preserved old elements it is obvious that the ground floor was vaulted and the eastern part was reconstructed many times. The largest tower is preserved with fewer interventions. It was a very important defensive element of the fortress, as it had room for a larger number of fighters and better visibility.
The ground buildings that are preserved in the internal yard were reconstructed relatively recently over the remains of the walls of the last building stage. They are successive rectangular rooms that were intended to house the soldiers or had other uses (storerooms, kitchens etc). They had a similar appearance during the Venetian rule, as it can be seen in maps. These maps also show the church of St Marcus in the yard of the fortress. However, G. Gerola noted that the ruins of the church were outside the castle on its southern side. Those were the foundations of the walls of a small building that had traces of wall-painting.
The church was destroyed during the restoration of the castle by Mustafa Naili pasha. As already mentioned, extensive reconstructions took place from time to time in Frangokastello. The first one is supposed to have taken place in 1593-1597 by the General Rector Nicolo Dona, while some years later extensive repairs were made by the Rector of Sfakia. In 1645, during hostilities with the Ottomans over the occupation of Crete, 1000 pounds were paid for fixing works. The most extensive interventions, however, were made by Mustafa pasha during the Cretan Revolution of 1866-1869. Interesting Venetian pottery items, mainly from the 16th century, coins and seals were found during cleaning works.