The original church in Warminster was a Saxon minster church, which existed by at least the early 10th century. The site is to the north west of the town, which is probably where the Saxon settlement was, and the town has grown away from its church. The earliest work found in the restoration of 1887-9 was a small window, believed to be of the 11th century. It is assumed that a stone Saxon church was replaced by a stone Norman one. The church was apparently re-modelled or rebuilt in the 14th century as a cruciform building with a central tower and a four bay nave, with aisles on both sides of the nave. Other additions were made in the late 15th or early 16th centuries.
By 1583 the church was in need of repair and by 1626 the whole building was described as 'decaying'. Extensive repairs were made in 1626-9 and the tower was repaired in 1638. These could not have been that good as in 1650 the building was then 'mightily in decay'. Work was done and a gallery built under the tower in 1660. In 1723-4 the arcade of the nave and the clerestory were demolished and rebuilt, while in 1745 the galleries were extended. The church met with the approval of visitors in the 18th century but by 1837 there were complaints about the differences of architectural styles and overcrowded pews. The curate, Daniel, thought that it was the ugliest church in the diocese of Salisbury.
It was largely rebuilt in 1887-9 by Sir Arthur Blomfield who left only the central tower, south wall of the chancel and south porch from the old church. Monuments from the 17th to 19th centuries were retained and the new style was Perpendicular. The outstanding 19th century vicar was Sir James Erasmus Philipps, 1859-1897, who founded St. Boniface's College and St. Denys's Home. He raised the money for rebuilding the church, founded St. John's Church and School in Boreham Road, the cottage hospital, orphanages and a girls' school. An average of 1,400 people attended his Sunday evening services.In 1986 rooms for children, a kitchen and lavatories were constructed in the church at the west end. The parish registers dating from 1556, other than those in current use, are held in the Wiltshire and Swindon Record Office.