The early history of the church is closely linked with that of St. John, under a single rector, and the phrase, 'the Church of St. John with St. Mary annexed, first used in 1400, is often found. The church was built in the 12th century to serve the new borough of Devizes, outside the castle area , which was served by St. John's. All that remains of the early church is the chancel, there being nothing dateable in the rest of the church earlier than the 13th or 14th century. From this period the church owned many plots of land in the town which provided a regular income.
There were radical alterations to the church structure in the 15th century when the walls were heightened, the south porch increased to two storeys with a stair turret and windows, buttresses and roofs replaced and renewed. The west tower was built against the nave. There were changes here during the Reformation including the removal of the rood screen in 1561. The church remained largely unchanged then until the 1850s when there was a restoration, the church was repewed and a vestry built.