The church consists of a W tower, nave with N and S aisles and a chancel with N and S chapels, and N and S porches. The lower section of the tower dates from the 12thc while the bell-stage is 13thc. The nave walls were rebuilt in 1846-1847 by William Burn. The N and S chapels of the chancel date from the 15thc. The N arcade of the nave is Romanesque.

The settlement appears as Stoke in the Domesday Book (in distinction to North Stoke) where it is assessed as taxable for 9 geld units. In the 1291 Taxatio it is also referred to simply as "Stok'", and the rectory is valued at £24, 8s, 4d.

The unusual treatment of the capital necking with its chamfer that goes up to the base of the cones is the same as that seen on the capitals of the chancel arch at the church of St Thomas Becket in Aunsby.