North Stoke is a cruciform church with a short, wide nave, S porch, N and S transepts and a chancel. Two blocked round-headed windows in the nave indicate that it dates from the late 11thc. or early 12thc.. The transepts have been dated betweenc.1270 andc.1330, and the chancel c.1240, on the basis of the window design. Two blind arches above a seat in the W wall of the S transept descend onto a corbel in the form of a lion's or ram's head, which may be reused. There is a shingled bell-turret on the N transept. There are three stone coffin lids carved with crosses in the churchyard.

North Stoke ('Stoch') and its church are mentioned in the Domesday Book of 1086. This is now a redundant church in the care of the Churches Conservation Trust. Until recently the dedication of the church was unknown, but according to the CCT website, a letter was discovered in 2007 from a bishop to King Edward I, naming it as St Mary's.

The corbel appears to be reused, and probably dates from the 12thc. The font was datedc.1200 by Nairn and Pevsner, which seems reasonable.