The church has a chancel with vestry and mausoleum to the N, a nave with clerestorey, N and S aisles and S porch, and a W tower. The chancel, which was lengthened in the 13thc. has traces of blocked, round-headed windows with rubble jambs and heads and may be Anglo-Saxon. The windows may have been double-splayed. The chancel arch and the W tower are probably early 12thc. (the tower has a blocked round-headed window in the ground stage of the S wall) and the nave was probably rebuilt at this time. Early masonry, bonded with the chancel masonry, survives at the E end of the nave. The current nave and clerestorey are 15thc. as is the top stage of the W tower and the S porch. The N and S aisles have 13thc. arcades, the N earlier than the S. Simple 12thc. sculpture is found on the chancel arch and there are fragments of string course on the W wall of the tower.
The Domesday Survey does not mention a church at Kempston, but records that Judith, the niece of William the Conqueror, held land there. VCH notes that Judith, or her daughter Maud, probably gave the church to Elstow Priory, which had been founded by Judith. Kempston is recorded among the possessions of Elstow Priory by 1218 (VCH, 304)