The original church is thought to date from the 12th century and was enlarged in the 13th century. During this enlargement a 13th century Gothic lancet window was installed, as were some Gothic pillars. In the 15th century further restorations were undertaken and a tower, south aisle and nave were added. In 1405 there were two silver chalices and two processional crosses. Three bells were hung in 1553, one in 1613 and a further two in 1899. The church was enlarged and restored in 1845. It is Grade II listed. The south transept, which was retained in the rebuild, is thought to be the original chapel. The original doorway also still stands in All Saints.
From 1678 to 1721, parishioners in Woodford were buried in wool, according to an Act of Parliament.
By 1845, the original Norman church was in a dilapidated state and the decision was made to rebuild it. The tower and south transept were retained. The cost of this rebuild was £1,241 and was met largely through private subscription, as well as a Church Rate of £250. The architect who designed the church was T.H. Wyatt. During this restoration, a fresco of St Christopher was uncovered on the north nave wall. New pulpit, pews and priest's stall were fitted and ashlar stone, probably from local Chilmark quarries, was used in the build. Electric lighting was installed in All Saints in 1932. There are now six bells in All Saints; the oldest dates from the 17th century.
The Flint Wall which runs along Church Lane, outside the church, was built by Mr Dyke in 1852 and cost £14.7s.0d. In 1884, parishioners erected a clock in the tower in memory of the recently deceased Reverend Robert Chatfield. He served for 52 years.
The churchyard to the west of the church was consecrated in 1896. The lych gate, the gateway covered with a roof on the entrance to the churchyard, was built in 1903 to commemorate the coronation of Edward VII, and the village cross commemorated the coronation of George V ten years later, in 1913.
There are several stained glass windows in the church. The windows in the north wall were designed by Sir Ninian Compton and were dedicated by Archdeacon Carpenter in April 1926. One window is in memory of Elizabeth Greville and one of George Greville, who was killed in France in 1918 in World War One.
The Old Vicarage was demolished and replaced in 1838. It had stood in a dilapidated fashion for at least a century and used to stand to the west of the church.
The parish registers from 1538 (marriages and burials) and 1546 (christenings), other than those in current use, are held in the Wiltshire & Swindon History Centre at Chippenham, as are the vestry minutes, which are complete from 1842.