Charlton was founded in Saxon times but if it had a church then the site has been long forgotten. The village was probably a planned settlement in medieval times but did not have a church and the inhabitants would have worshipped at nearby Standlynch church or have travelled to Downton. It was not until 1851 that the Church of All Saints was built, partly at the expense of Horatio, Lord Nelson, to serve the tithings of Charlton and Witherington. It is in the Early English style, in red and purple brick, and was designed by T.H. Wyatt. There is a chancel, a nave with a north transept that was added in 1891, and a south porch.
This was a perpetual curacy, in the gift of the vicar of Downton, and Lord Nelson's private chaplain became the first curate. By the 1860s the average number of communicants was 55. In 1969 the tithing of Witherington was transferred to Alderbury and the church served Charlton alone. The church is now part of the Chalke Deanery. The parish registers from1851, other than those in current use, are held in the Wiltshire and Swindon History Centre at Chippenham. Earlier records are likely to be in the Downton registers.