It is the mother church of the large ecclesiastical parish of Redenhall-cum-Harleston and Wortwell, with the smaller church of St John the Baptist in Harleston originally being a chapel of ease to Redenhall.

[2] The site of St Mary's, Redenhall has been used for worship for around 1000 years or more, with the lines of an earlier round-tower church of Saxon or Norman date discovered in 1858 beneath the nave arcades and chancel step when a new heating system was being installed.

The chancel is the oldest part of the present building, dating from the early 1300s and possibly built as an addition to an earlier church.

The 15th and 16th Centuries saw a period of grand church building and rebuilding throughout East Anglia, the present nave and aisles dating from this time.

This article about a church or other Christian place of worship in England is a stub.