Although records of the church go back to about 1200, it has been repeatedly rebuilt; the oldest surviving fabric dates to 1658, but a majority of it is from the early 19th century.

Strype's predecessor, Samuel Keme or Keene, was also a cavalry officer in the New Model Army during the First English Civil War and was said to have preached sermons at Leyton while wearing his military buff coat.

In 1658, the old bell tower, which was in danger of collapse, was replaced by the present one built of red brick and a north aisle was also added of the same material.

[1] Despite these measures, in 1822 the vicar complained that lack of space in the church during services meant that "small traders, labourers and servants" were forced to "sit or stand in the aisles, to the great inconvenience of themselves and others".

[3] Accordingly, a new brick south aisle was added with the distinctive Y-shaped window tracery visible today, designed by John Shaw.

[4] A chancel arch and clerestories were constructed of timber framing covered with lath-and-plaster, and supported on slender cast iron columns.

The whole church was reroofed, the chancel being increased in height to conform and battlements were added to the tower,[1] which had already been heightened in 1806 by the addition of an 18th century cupola taken from Leyton Great House.