The church of St Mary was built at the edge of the outer bailey of the castle, and was clearly designed to serve the expanding town.

The 12thc chancel, built in ashlar, has survived later rebuilding campaigns. It is two bays long, vaulted, and was originally decorated on the interior with an intersecting blind arcade, most of which has now been removed. On the exterior, there are pilaster buttresses and the remains of a corbel table, but the 12thc windows have been replaced, probably twice in the case of the E window.

The S porch of the 15thc nave includes an external arch with a series of reset 12thc stones, possibly from the chancel arch which was replaced in the 15thc when the nave was rebuilt.

The roof line of the earlier nave, probably 12thc, can be seen on the E wall of the W tower. The W tower also belongs to the 15thc. The chancel was restored in 1852.

The history of the church of St Mary is closely linked to that of St John the Baptist, the church that was built in the inner bailey of the castle, perhaps originally to serve as the garrison chapel, while St Mary's served the town. In 1194-95 the churches are described together as ecclesie, but by 1226-28 they are called capelle. In 1268 John, chaplain of the king's chapel, held both churches. However, there is evidence only for St Mary's holding plots of land in the medieval period (VCH 1975, 285-314).

The date of the present nave is suggested by an inscription in the roof which attributes the work to money provided by William Smythe who died in 1436.

Surviving 12thc chancel: some authors believe that this church predates the more accomplished nearby chancel of St John the Baptist but St Mary’s seems to be a less skilful, and therefore possibly a cheaper reflection of the chapel. St Mary’s follows, in form and detail, the lead of St John the Baptist but inexpertly. An example of this is the asymmetrically placed upper window/ventilator which is an obvious borrowing from its larger neighbour, but the failure to place it centrally demonstrates that the direction of the project was less accomplished. (Fieldworkers)

As the chancel arch was replaced in the 15thc, the fragments from the original arch could have been available for reuse in the porch. The form of the label with the dragon's head, is also found in buildings derived from Old Sarum and Malmesbury. (Fieldworkers)