The church has chancel (with modern vestry on N), nave, N and S aisles and W tower. The 13thc. chancel (extended in the 14thc.), has a late 12thc. chancel arch with keeled respond shafts and stiff-leaf capitals. The nave was originally aisleless, and the quoins surviving in its outer W wall may date from the 11thc. The N and S aisles are 15thc., as is the W tower. The church was extensively restored in 1875 by Ewan Christian. The late 12thc. S doorway, reset when the aisles were built, has also been restored.

The Domesday Survey does not mention a church at Caddington, but records that the Canons of St Paul, London, were granted the Manor by William I. The advowson of the church of Caddington was held by St Paul's by 1183–4 although VCH suggests that it was held by them prior to this date (VCH, 319-20). The grant was confirmed in 1254 by the Bishop of Lincoln.

In 1086, Caddington was partly in Hertfordshire (10 hides) and partly in Bedfordshire (5 hides). It was transferred wholly to Bedfordshire in 1897.

Pevsner suggests that the quoin stones surviving in the outer W wall of the nave may be Anglo-Saxon, but Hare states that the side-alternate quoins are a type used throughout the medieval period. Both Pevsner and VCH proposes a date of 1180-1200 for the doorway.