Heston has been a place of Christian worship since the 7th century when Theodore, Archbishop of Canterbury, sent two priests (probably Benedictine Monks) to the Manor of Gistelesworthe (now known as Isleworth), with one arriving in Heston.

In 1086, the manor was given to Walter of Saint Valéry by William the Conqueror; the church was later given to the Abbey of Saint-Valéry (Picardy, about 20 miles from Dieppe). The church would have been built sometime between the end of the 11th century and 1227, when the parish of Heston was first recorded, and would have preceded the church whose tower still survives.

The dedication of the parish church to St Leonard goes back to the early 13th century and seems to have been a result of the establishment of a priory in Hounslow for friars of the Trinitarian Order. The Trinitarians were noted for their work in securing the release of prisoners - and the patron saint of prisoners is St Leonard.

Over the years, the patronage of Heston Church had moved between Winchester College and the Crown. The final transfer of Heston happened during the rule of Elizabeth I, where it was passed to the Diocese of London, with the Bishop of London remaining the current patron.

The current church building is a Grade II Norman Church, rebuilt in 1867 from some of the original material and retaining many of the original features. The rebuilding took approximately one year; the new building was consecrated by the Bishop of London in May 1867.

The entrance to the church and churchyard is through a 15th Century, Grade II listed lych-gate.