The fortress of Agios Nikolaos of Kyriakosellia is located in the homonym settlement of Kyriakosellia, belonging to the province of Apokoronas. It was a Byzantine fortress built by the feudal lord of the region to secure his privileges.
In 1092AD, the Byzantine ruler Skordilis got the area of ??Armeni, Stylos, Kalives up to Keramia village under his feudal possession. In order to ensure his privileges, Skordilis built an impregnable fortress on a hill near Kyriakosellia. The hill was steep, accessed only from the west and was also supported by a powerful circular tower.
When the Genoese pirate and count of Malta, Henry Pescatore, occupied Crete, he built or repaired and equipped 15 fortresses around Crete. One of these was the fortress of St. Nicholas. But even when the Venetians expelled Pescatore from Crete (1211), they restored the fort.
During the revolution of 1217, which was led by Constantine Skordilis and Michael Melissinos, the rebels occupied the largest part of western Crete. The fortress of St. Nicholas became a property of Skordilis family again.
Revolutions against the Venetians in the early years of the Venetian Era were consecutive. During one of them in 1234-1236, the Venetians, led by Gradenigo, defeated the rebels and reoccupied the whole island. The only fortress of Crete where the two-headed eagle of Byzantium was waving was the fort of St. Nicholas in Kyriakosellia. On July 23, 1236, Skordilis family agreed to quit the fort, so as to keep his privileges.
Today only a small part of the walls and the small church of the fortress are remaining.