St Mary's is a large cruciform church of the fenland. Like many parish churches, the fabric of Sutterton reveals a long history of transformation and renovation. The chancel and clerestories of the transept, and the N transept, are of the 13thc. though the chancel was restored in 1879 by James Fowler. From the exterior the nave and aisles are of the 14thc./15thc. A major restoration in 1861-63, carried out by Edward Browning, included the rebuilding of the tower, spire, aisle walls, S transept, and chancel. The S porch was added in 1861. The Romanesque survivals here are extensive: the N and S doorways into the nave, portions of the five-bay nave arcade, and the W crossing arch, and the E responds of the S and N crossing arches.

There is no mention of Sutterton in the Domesday Survey.

In a very subtle, but significant design shift the sculptor who executed the label of the S doorway changed the ear position on the beast head label stops in order to give continuity to the straddling chevron motifs: the ears mirror the start and end direction of the straddling chevron which start wide on the L side, hence the spread beast ears, and finish in a point on the R side, hence the beast ears leaning in and meeting at a point. Straddling directional chevron is also used in the label of the bay 3 arch of the N arcade in the nave suggesting a continuity of workshop in the construction of the S doorway and of the nave. The N doorway of the nave is extraordinary in its variety of sculptural forms making it one of the richest Romanesque survivals in the county. The complex label with beast-head (dragon?) stops, and even to some extent the treatment of the foliage on the third order, E capital, recall the N portal on the W façade at Lincoln Cathedral with its beast-head label and its second and third order imposts of upright acanthus foliage. Why such an ornate N doorway?

N arcade: the human heads on the pier 2 capital are extremely well-proportioned and wonderfully expressive. In the nave, two previous roofline levels can be seen above the chancel arch. The lowest one may correspond to the roof level at the time when the nave arcades were first erected at the low height of their E responds. Above the present arcades is a roll mould string course which terminates at the chancel wall at the same height as the second roof line. It has been suggested by D. Stocker that there are stylistic affinities between some of the sculptural work at St Mary's Guildhall in Lincoln and the acanthus volutes in the arcades and the acanthus trails in the N and S doorways at Sutterton. The imposts of the W crossing arch are at the same high level as the imposts of the nave piers compared to the lower level of the nave arcade E responds. This height differential, along with the heightening of the nave roof; the predominance of pointed, chamfered arches in the nave arcade and crossing arches; the use bell capitals in the E, S, and N crossing responds; and the elaborate, hybridized waterleaf capitals could point to a major rebuilding and expansion of the church around 1200.