This is a large Fenland parish church. The evidence of the lancet windows and a clerestory lancet headstone suggest that the chancel and nave were rebuilt during the 13thc. The S arcade is of the 14thc. while the N arcade, clerestory, and W tower are all later medieval work. There was a major restoration in 1853-54 under the direction of the rector, Rev. Henry Holdsworth during which the S porch was completely rebuilt and the vestry added. Extant Romanesque features are the priest's doorway, segments of the chancel string course, and numerous re-set stones in the chancel, nave, and aisle walls.

The Domesday Survey records that among the land held by Guy of Craon, the village of [Fish]'Toft' had both a church and a priest in 1086. Thompson, following Dugdale's Monasticon, cites a 12thc. charter in which Alan de Croun presents the church at Toft to Croyland Abbey (along with Freiston church and others) for the founding of a cell of monks from Croyland; this cell was established at Freiston.

The insertion of the 13thc. lancet window directly above the priest's doorway has resulted in the square door heading here. The fluted E capital on the priest's doorway is similar to those used by Fowler for his reconstruction of the S aisle doorway at the neighboring church of Freiston, St. James. Thompson notes that the re-set stones inside the church were discovered in their current positions when the plaster was removed from the walls during Holdsworth's renovation of 1853-54.