There may have been a Saxon church here and there was definitely an 11th century church. What remains of the Norman church is the arch of a doorway and some other carved stonework that has been reset. The carving dates from c.1125 and shows 2 women holding a cross, possibly representing the 'Invention of the True Cross'. The Norman and medieval church was built in stone with a nave, chancel, a north chapel, a north porch, and with a later mortuary chapel for the Eyre family to the south. There was a small weather boarded west belfry. The church is near the present Landford Manor and there may have been small houses close to the church in medieval times, if there was a nucleated settlement here.
On 11th January 1689 there was a violent wind that blew down a great elm tree that fell on the nave and chancel, destroying much of the roof. The cost of repairs was £33 for the nave and £3.10.0d (£33.50p) for the chancel, although the wood from the tree was sold for £10. A hole made in the north wall, to the east of the porch, was made into a window and the church was re-opened on 8th June. Being close to the New Forest, Landford was frequented by gypsies, particularly the Stanley family, and a Queen of the Stanley tribe is buried in the churchyard. Mary Stanley died in 1797, aged 60, and her headstone can still be seen.
The Kelly's Directory of Wiltshire for 1855 states that, 'The church of St. Andrew presents nothing worthy of notice' and in 1856 the church was so dilapidated that the Vestry meeting decided that it was past repair. Subscriptions were started to build a new church on the site with Countess Nelson giving £1,000 and the Rev. Henry Girdlestone giving £100. The architect was William Butterfield and the builder John Crook of Whiteparish. The church was almost entirely rebuilt at a cost of £1,490 with beams from the earlier church being used for woodwork in the porch. The new church had a nave, chancel, south transept, vestry, a south chapel containing monuments from the old church, a porch and a bell turret with 3 bells. It was consecrated on 7th October 1858. In 1882 the building was enlarged by raising the roof of the vestry and creating a north transept while adding a new vestry to the east. By 1927 there were 6 tubular bells in the turret. The parish registers from 1671, other than those in current use, are held in the Wiltshire and Swindon History Centre at Chippenham.