This small and beautiful church was situated just inside the Saxon town wall. Its early history is unknown but it is unlikely to have been a parish church, although there was probably an early chapel on the site. There was definitely a Norman church here as can be seen from the chancel arch of c1120-50. Evidence found during restoration indicates that the early church was burned down and rebuilt in the transitional Norman style of the mid to late 12th century. The church has a fairly low tower, with the two lower stages of the late 13th century and the top stage and buttresses of c.1400. The walls of the north aisle are 13th century but both north and south aisles were rebuilt when Perpendicular windows were inserted in the late 14th or eary 15th centuries. The small chapel on the northern side of the chancel was probably built c.1450.
The restoration of 1862 was by Galpin, a pupil of Pugin, who removed the galleries, cleaned and repaired the carved oak in the church, rebuilt walls and opened up the oak roof to view and renovated it. There is a fine 14th century limestone churchyard cross with carved figures on the base representing the Crucifiction, St Mary, a bishop with an unidentified figure and two other figures. The church had three bells in 1553, which were recast and rehung in 1780. St. Mary's was the smallest parish in the Bristol diocese, covering only 121 acres with few parishioners. In 1952 it was united with the parish of St. Sampson and in the 1970s St. Mary's was declared redundant. From 1984 the church has been leased to the Catholic congregation in Cricklade and it is now the Roman Catholic Church of St. Mary. The parish registers from 1684 (christenings), 1686 (marriages) and 1683 (burials) are held in the Wiltshire and Swindon History Centre at Chippenham.