The church standing at Newton Tony dates from the 19th century and replaced a much earlier church. It is dedicated to St. Andrew and was built in 1844 in a 14th century style. The original church was demolished in 1843 to make way for it.
There was a churchyard of some kind in Newton Tony in 1179 although it is not clear if there was a church at that point, although there was a church in Newton Tony by the end of the 12th century. The first recorded rector was Richard Baret in 1299. The advowson - the right to appoint vicars to an ecclesiastical parish - passed with the manor of Newton Tony until the 17th century. Occasionally, the Crown intervened, and the King presented the rector.
Cock fighting was allowed and encouraged by the churchwardens in 1621; this took place in the chancel.
St Andrew's retains a Norman font from the original church and the new church cost £1,100 to build in the 19th century and was designed by architects Wyatt and Brandon. It is now a Grade II listed building. The pews were saved from the original church and installed in St. Andrew's. There were family pews for the Malet and Poore families. There are stained glass windows in the chancel. On Census Sunday in 1851, the afternoon service was attended by 114 people.
There are many heraldic tablets in the church, celebrating the local Malet family. There is a wall monument dedicated to Dame Marian Dora Malet, including a portrait bust, of according to author Arthur Mee, a 'lady of great serenity'. There is a tablet for George Malet, who after his death in Persia in 1856, was remembered when his sword and scabbard were hung in the church. One memorial is to Celia Fiennes, who died in 1741, who was a local lady who travelled across the country writing her journals. The communion plates are from the 17th century.
In May 1999 the church organ was replaced. It was paid for by Lady Iveagh, of Wilbury Park Estate. The organ wasn't actually new, but had been repaired and restored after being used in churches in Sunderland and Nottinghamshire. It took two men three weeks to install it in St. Andrew's. There was a service celebrating the organ on 27 June 1999.
The church was repaired in 1904; this was done to honour the memory of Sir Harry Eden Mallet. More repairs were necessary in the 1970s. £4, 250 was necessary to repair the church fully, after £1, 156 had already been paid out, and most of this money was gained through fundraising by the St. Andrew's Church Appeal. Electric lighting was first installed in the church in 1953. There are four bells in the tower and tenor bell is especially interesting and came from the Salisbury Foundry in the 17th century. The new rectory was built in 1778, after the previous house had fallen into a bad condition. It is a red brick house with two storeys and is a Grade II listed building.
The parish registers from 1568 (burials), 1586 (christenings), and 1591 (marriages), other than those in current use, are held in the Wiltshire & Swindon History centre at Chippenham.