The Domesday Survey of 1086 records that Sutton had a church and was held by Count Eustace III of Boulogne. Through the Count's granddaughter Maud, who married King Stephen, the property passed to the Crown. In 1136 the King made an exchange of land with his brother Bishop Henry of Blois, swapping Bishop's Sutton for Steeple Morden in Hertfordshire. Bishop's Sutton remained with the diocese until 1551.
Bishop Henry rebuilt the existing church and erected a palace to its N. Historians have speculated that the palace was destroyed during the Civil War.
The nave of Bishop Henry's church survives, but the chancel was rebuilt in the 13thc. The building was restored in 1891-93 by G. C. Awdry and in 1961-62 by Potter & Hare.