The church consists of chancel and nave separated by a tower, N and S aisles and N transept. There are substantial remains of the original Anglo-Saxon church which consisted of chancel, nave and a square W porch (which formed the lower stage of the tower). The chancel of the original church no longer exists, and the W part of the nave became the chancel of the present structure. The tower has long-and-short quoins visible on its lower W face, and rubble quoins on the upper stages. The NW and SW angles of the chancel also have long-and-short quoins. Both structures have blocked round-headed, double-splayed windows. The windows on the tower, two to each face, lie in the stage below heavily restored, but originally 12thc., bell openings. On the E face of the tower is a triangular-headed opening, containing a reused fragment of Anglo-Saxon carved stone in its N jamb. The nave and aisles, originally medieval were completely replaced in 19thc. 12thc. sculpture is found on the reset S doorway, brought to this site from the church of St Peter de Dunstable (VCH, 25) which was pulled down in 1545 (Lyson, 53). St Peter de Dunstable was sited near St Mary, Bedford.

The Domesday Survey does not mention St Peter, Bedford. VCH records that the advowson of St Peter was granted to Merton Priory in the early 13thc.

Magna Britannia states that the stones from St Peter de Dunstable were used in repairing St Mary's Church, Bedford, mending the streets and repairing the bridge.

A photograph taken before the 20thc. porch was erected over the S doorway shows that the doorway was framed by an ashlar panel with two tiers of shafts on the angles, the upper shafts had masks in place of capitals, the lower shafts had cushion capitals with an inverted lily in the shield. Much of this structure was removed to accomodate the porch and what remains seems to be restored. An etching of 1820 (Fisher), gives a schematised outline of the doorway including the ashlar panel, demonstrating that this was in place prior to the restorations of c.1850.