The fort Castel Nuovo (or Kenourgio Castelli) was built on the isolated hill Psilo Kastelli, northwest of the village Kastelli, province Kenourgiou, near Phaestus. The fort was built by the Genoese pirate Enrico Pescatore in 1206, who named it Nuovo (i.e. New), probably because it was one of the fortresses he built from scratch, without another preexisting. It is believed that this is the site of the ancient city Aena. The entrance to the fort was located on the south side of the hill, where there was a steep staircase.
During the Revolution of two Syvritos by the noble families Melissinos and Skordilis (1230-1236) against the Venetians, the fort was occupied by the rebels, after a fierce siege of the castellan Corrado de Milena. During Kallergis revolution (1363-1367), the rebels tried to occupy the Castel Nuovo, but in vain. As the number of movements against the Venetians decreased, the fort lost its importance and was eventually abandoned. Only during the Cretan War (Venetian-Turkish war) it was reused.
The name of the castle was also used for the current name of Kainourgiou Province. Today the fort is ruined and severely damaged, with only a few parts of the walls and water tanks surviving.