The church, originally cruciform with an aisleless nave, now has chancel (with N chapel or vestry), crossing tower, N and S transepts, and nave with N and S aisles. The earliest surviving feature of the church is the S transept which has late 11th to early 12thc. splayed, round-headed windows in the E and W walls. Masonry of this date also apparently survives in the N transept. The E window of the S transept (unblocked in 1959) cuts into an even earlier, blocked, round-headed window. The crossing tower may also be of early date. The twin bell-openings of the first stage of the tower are late 11thc. or early 12thc. The top stage of the tower has Perpendicular openings, and traces of earlier, round-headed openings (two on each face) flank these. One of these openings, on the W face of the tower, has an arcuated lintel. The chancel is late 13th to early 14thc., the N aisle is 16thc. and the S aisle is modern. The tower arches and S aisle were restored in the 19thc. A carved head corbel, now in Bedford Museum, was found in 1959 when workmen were engaged on repairs to the S transept (see Bedford Museum).

Late 11th to early 12thc. sculpture is found on the bell-openings.

The Domesday Survey does not mention St Mary, Bedford, although there is a reference noting that the Bishop of Lincoln held 'Bedford Church' (DS 4, 9), and VCH records that the Bishop of Lincoln had a charter from William I, granting him the advowson (29). VCH records that in 1200 the Bishop of Lincoln and the Prior of Dunstable both laid claim to the advowson of St Mary and that both had charters demonstrating their claim to the church. The dispute was resolved and the Bishop retained the advowson whilst granting a yearly pension of 20s to the Prior of Dunstable.

VCH suggests that the irregularity in the plan of the church indicates that there was an earlier structure on the site and that the tower sits over what would have been the orginal chancel, but this theory is no longer supported.

The fact that the crossing tower and S transept are in alignment with each other but not the rest of the church, supports the idea that they were part of one campaign of construction and the rest of the church of another campaign. Smith suggests, on the grounds of the architectural evidence, that these early features could be dated between 1075 and 1115 (Bedfordshire Archaeological Journal, 9, 97). The early E window in the S transept, cut into by the a later round-headed window is probably 11thc. although not necessarily pre-Conquest. The same might apply to the blocked windows in the tower.

The sculpture on the bell-openings includes at least one voluted capital, which probably indicates a late 11th to early 12thc. date.

Smith notes that St Mary, Bedford, is one of a number of Saxo-Norman overlap churches lying along the River Ouse (Bedfordshire Archaeological Journal, 9, 98).