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 between c.1270 and c.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.
