The fortress of Agios Nikolaos is located at the village Kyriakosellia, province Apokoronas in West Crete, which is well known for the Byzantine church of Saint Nicholas at Kiriakoselia. It was a Byzantine fortress built by the feudal lord of the region to secure his privileges. In 1092, the Byzantine local lord Skordilis got the area of Armeni, Stylos, Kalives up to Keramia 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, Henrico Pescatore, occupied Crete, he built or repaired and equipped 15 fortresses around Crete; one of these was the fortress of Agios Nikolaos. But even when the Venetians expelled Pescatore from Crete (1211), they restored the fort and used it for defense.
During the revolution of Skordilides in 1217, which was led by Konstantinos Skordilis and Michael Melissinos, the rebels occupied the largest part of West Crete. The fortress of Agios Nikolaos 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 still waving was the fort of Agios Nikolaos in Kyriakosellia. However, in July 23, 1236, Skordilis family agreed to quit the fort, so as to keep their privileges.
Today, on the hill only a small part of the walls and the small church of Saint Paraskevi are surviving.