Sections of the chancel and the aisle date from the early 13th century, as does the chancel arch, which was moved to become the tower arch when the church was rebuilt by T.H. Wyatt in 1861-2. The arcade dates from the 13th and the 14th centuries. The tower, which possibly dates from the 12th century, was rebuilt in the 14th century. In the early 19th century a vestry/schoolroom was added to the south side of the chancel but was removed shortly afterwards. The mid-19th century rebuilding, financed principally by the Pembroke family, largely retained the general form of the medieval church.
In 1553 the church was recorded as having four bells. Of these two, cast in Salisbury, still hang in the church. Bells cast in 1603 and 1610 replaced the other two. A fifth bell was added in 1862 and a sixth in 1887 when the 1603 bell was also replaced.
A vicarage house in existence in 1598 was described in 1609 and 1705 as a small thatched house with three rooms on each of its two storeys. A new vicarage built in the late 18th century was demolished in 1865 and a new one built north of the church; this was sold in 1981.
By 1191 a prebendary held the estates belonging to the church. A vicarage was ordained by 1325 and from that date until 1450 the advowson was held by the prebendary. In 1450 Wilton Abbey appropriated the prebend and also held the advowson from this date until the Dissolution. Patronage subsequently passed to Sir William Herbert and descended with the manor of South Newton and the Pembroke title. Since 1992 the church has been part of the benefice of Lower Wylye and Till Valley, which is shared by the Earl of Pembroke.
The tithes received by the vicar of South Newton included wool, lambs and hay; in 1844 the value of the tithes were placed at £280.
The vicar of South Newton also acted as chaplain of Wilton union workhouse and held services there on Sunday and Friday each week. The workhouse chapel was built in 1864. In the first quarter of the 20th century the workhouse was converted for the accommodation of mentally handicapped people. South Newton vicars continued their chaplaincy until the late 1930s when the buildings were converted to commercial use. At the end of the 20th century the former workhouse chapel became Wilton Spiritualist Church.
Parish registers and Bishop's Transcripts survive from 1604 and, other than registers in current use at the church, are held in the Wiltshire & Swindon History Centre at Chippenham.