In the Domesday Book of 1085, mention is made of two priests in Leyton, which implies the existence of a church building, but the first surviving record of one is in circa 1200, when the church and manor of Leyton was granted to Stratford Langthorne Abbey. The first evidence of a vicar is in 1254 when the annual income was only 40 shillings, most of the revenue from tithes going to Langthorne Abbey and Holywell Priory in Shoreditch. A vicarage existed in 1537 on a site at the present junction of Vicarage Road and Leyton High Road. By 1650, it was reported to be dilapidated and was subsequently rented to a poor woman. In 1677–1678 a new vicarage was built in its place, partly funded by John Strype, a well known antiquarian. Strype had been appointed as curate in 1669 in the absence of a vicar, a post that he held for 68 years until his death in 1737. 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. The foundations of the medieval church building were uncovered in 1962 and consisted of a nave and chancel that were so small that they lie within the area of the modern nave. 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. In 1693, the chancel, which was too narrow for the people to receive Holy Communion from, was rebuilt in brick with a circular east window. In 1711, the gallery at the western end was rebuilt and enlarged and in 1817, another gallery was erected in the chancel to accommodate one hundred boys of the Sunday school. 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". Although plans had been drawn-up for the enlargement of the church in 1811-1812, but they had not been proceeded with through lack of funds. However, in 1822, an anonymous benefactor known only as "The Old Parishioner" donated the enormous sum of £1,000, and donations from other parishioners more than doubled that amount, allowing work to commence. Accordingly, a new brick south aisle was added with the distinctive Y-shaped window tracery visible today, designed by John Shaw. 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, which had already been heightened in 1806 by the addition of an 18th centurycupola taken from Leyton Great House. Other improvements made at the same time included the purchase of a pipe organ and the construction of a new vestry room and churchyard walls. In 1853 a new east window was made and in 1884 a new baptistery was built in the south-west corner. During restoration work in 1889, a new altar and stained glass for the east window were donated. In 1920, an oak chancel screen and an altar-piece representing Leonardo da Vinci's The Last Supper, were installed as a war memorial. An ambitious programme of restoration began in 1929, which included lengthening the nave, replacing the lightly-built chancel arch and clerestory in concrete, encasing the iron columns in concrete and inserting oval windows into the sanctuary. In 1935, the old vestry was restored and an oriel window was added over the south door. Bomb damage, including to the tower parapet, was repaired in 1951. The nave was refloored in 1961 and the chancel screen was moved to the west end of the nave two years later. Following a fire in 1995, a chapel was created under the tower and the baptistry and south entrance were remodelled. The church contains a number of monuments to eminent past parishioners, including Sir Michael Hicks, his wife and his son, Sir William Hicks. A monument to William Bosanquet is by John Flaxman and another to William's son Samuel Bosanquet is by John Pasco. There are also monuments to Sir John Strange, Sir Henry Cheere, Sir Richard Hopkins, Sir Robert Beachcroft and Charles Goring, 2nd Earl of Norwich. St Mary's was the only Anglican church in the ancient parish of Leyton until 1749 when a chapel of ease was opened in Leytonstone, later rebuilt as St John The Baptist's Church, which was made a separate ecclesiastical parish in 1845. By 1903 there were nine Anglican parish churches and twelve missions churches in the district. Over subsequent decades, the churches of St Edward in Morely Road closed in 1968, and St Luke's Church in Ruckholt Road closed in 1982 and their parishes were reunited with St Mary's. The church became a Grade II* listed building in 1954
