There was a Saxon church here and it is likely to have been built before 940 as it was described as being on the royal estate. Pewsey had been held by King Alfred (died 899) and it descended in the royal family until given to St. Peter's Abbey at Winchester in 940. It is said that on his return from a victory over the Danes, King Alfred announced from the church door that the day (14th September, Holy Cross Day) should be a feast day forever, and that this is the origin of the famous Pewsey Feast. By 1086 the small estate attached to the church was held by Rainbold the priest and a Norman church with a nave, chancel, and, possibly an apse, replaced the Saxon one. It is possible that the foundations of sarsen stone may have come from the Saxon church. The nave is of the 12th century and two aisles were added later, probably in the 13th century. The chancel was rebuilt in the later 13th century as it had collapsed; the chancel arch and the western part of the south arcade were added at the same time. In the 14th century the nave roof was rebuilt and a clerestory formed at the same time.
The tower was built in the early 16th century while in the 17th century the south aisle roof had to be renewed. The population must have expanded in the late 17th and early 18th centuries as galleries had to be built to accommodate more people. A west gallery existed by 1710, one was built in the north aisle c.1738 while one in the south aisle may have been constructed in the early 19th century. The porch was repaired or rebuilt in 1804-5 while, after complaints about the draughts through the nave roof, a flat ceiling was built in the nave at a cost of £200. There were three 19th century restorations. In 1853, using the designs of Thomas Candy, the floor was lowered, the north and west galleries rearranged and the vestry altered. In 1861 the chancel was largely rebuilt and the south chapel added, under the architect G.E. Street. The major restoration was under Wiltshire architect C.E. Ponting who demolished the north aisle and replaced it with a wider one, exteding it to the east to create a new vestry and organ chamber. The north and south galleries were removed, as was the nave ceiling, and the nave was reroofed making it weatherproof. The roof of the vestry and organ chamber came from Ivy Church priory and were given by the Earl of Radnor.
The works of the early 17th century clock had been removed and placed in the lower part of the tower in 1958 and clock was restored in 1982. Nearby is the 12th century Norman font with its elaborate top, carved by Canon Bouverie (rector 1880-1910). There is an haioscope, or squint, in the chancel arch so that people in the south aisle could see the altar. Outside the churchyard is small and set high above the road. High on the west side of the tower, which contains 6 bells, is a carved lamb, often a feature on churches dedicated to St. John the Baptist. The parish registers dating from 1568 (baptisms and burials) and 1569 (marriages), other than those in current use, are held in the Wiltshire and Swindon Record Office.