The church has a broad nave and chancel, both without aisles and of the 12thc, and a W tower rebuilt 1936-37. The 12thc work is of rubble and good ashlar masonry. Romanesque sculpture is found in the blocked S doorway and blind arcade above; in the blind arcade above the plain round-headed doorway on the N side of the nave, the latter within a modern timber porch; on the string courses around the buttresses; and on the font. There is also a plain round-headed chancel arch with plain grooved impost blocks.

Before the Conquest Stoulton belonged to the bishop of Worcester's manor of Kempsey, and was assigned to the support of the Worcester monks. In 1086 it was held by Urse the Sheriff under the bishop of Worcester. Stoulton was formerly a chapelry of Kempsey church.

Blind arcades in frontispieces above the doorways are found in other churches in the area (cf. Knighton-on Teme, Bockleton, Eastham). The VCH suggests a date of c.1120, Pevsner of c.1130-40. The S doorway is more elaborate than the N one, and was probably once the main entrance. A build-up of the ground on the burial side may account for the change of use. Doorways set in a projecting bay, as here, occur in a number of churches in the county (see Preface to Worcestershire).