Evidence for an early church on this site exists in the form of a 12th century capital now incorporated in the wall of the early 13th century nave. The present chancel was built in the later 13th century and has a fine complete Early English piscina. St. Mary's is one of only three parish churches in the country that has both a central tower and spire and a western tower. The others are at Wanborough in Wiltshire and Ormskirk in Lancashire. The central tower was built in c.1325 and the transepts were also added in the 14th century. The chapel on the southern side of the chancel is mid 14th century and the decorated piscina indicate that it was a chantry chapel.
In the 15th century the north and south aisles were rebuilt and the nave walls raised by about three feet. The west tower was built in the latter part of the 15th century and the building of this caused alterations to be made to the chancel. The south porch originally had three stories but the top one was removed in the restoration of 1872. The present upper floor was a priest's room. The church has possibly had three dedications as in a document of 1336 it is referred to as St. Nicholas and there is also a local tradition that the dedication was to St. Michael. The fact that the village feast was on St. Michael's day, and therefore any annual fair is likely to have been on that day, supports this tradition.
The 1872 restoration was carried out by Butterfield and included rebuilding three walls of the chancel. During the work the walled up skeleton of a woman was found in a room or chapel in the north transept. The reason she was there remains an unsolved mystery. In 1977 wall paintings were uncovered and the best of these being the Death of the Virgin on the south wall of the Lady Chapel. There are six bells in the west tower, the oldest being of 1598, and three sratch dials on the south walls of the transept and Lady Chapel. Inside the church is a memorial to Nevil Maskelyne, the former Astronomer Royal who died in 1811. Outside the church are the remains of the steps, base and stem of a churchyard cross.
Parish registers from 1558 (marriages and burials) and 1564 (baptisms), other than those in current use, are held in the Wiltshire & Swindon History Centre at Chippenham.