The church is first mentioned in 1319 but the existence of a Norman font, now in St. Paul's Church, suggests a much earlier foundation. Much of the structure of this largely flint church was of the 13th century, with a nave, north aisle, north and south transepts, a chancel and a west tower and south porch. The belfry stage of the tower was built in the late 15th or early 16th century and there were some windows in the Perpendicular style. In 1824 it was said to be an 'unassuming village church'. In 1850 the vestry met to consider building a new church to house the expanding population of the area. It was decided to build the Church of St. Paul in Devizes Road and St. Clement's was demolished in 1852. The churchyard remained an open space on the western side of Mill Road. The tower buttresses, some of the interior arches, piers and the font were used in the new church of St. Paul's. The bell frame timbers and the six bells were also used in the new church and various monuments were transferred there. The parish registers from 1654 (christenings and marriages) and 1653 (burials) are held in the Wiltshire and Swindon Record Office.