The original 12thc. church consisted of a chancel and an aisleless nave. Some of the original quoin stones have been reused in the NE and SE angles of the nave. The church now has chancel with 19thc. N vestry, and nave with N arcade of c.1300 (the aisle is 15thc.) and S arcade of c.1330 with a 15thc. W bay (the aisle is late 14th to early 15thc.). The W tower is mid 15thc. and the chancel was rebuilt at the end of the 15thc. A reset plain 12thc. window with an arcuated lintel is found in the N wall of the vestry. 12thc. sculpture is found on a finely carved pillar piscina.

The Domesday Survey does not mention a church at Henlow, but records four land-holders: Nigel de Aubigny, Walter of Flanders, Azelina (Wife of Ralph Tallboys) and the Burgesses of Bedford. Herfast held land of Nigel de Aubigny, and Herfast's son Nigel along with the de Aubigny family gave Henlow church to Llanthony Priory (Gloucestershire) (VCH, 281). This was confirmed in 1199 by King John. Llanthony Priory retained the advowson until the Dissolution.