Until the early 19th century, the hamlet of Blackheath south of the common was served by churches in nearby Greenwich, Lee, Lewisham and Charlton.

Land on the southern edge of the common was donated by William Legge, 5th Earl of Dartmouth, and he laid the foundation stone on 26 October 1857.

On All Saints’ Day, 1 November 1858, the Bishop of London, Archibald Campbell Tait, consecrated the church, which had been designed by the architect Benjamin Ferrey;[1] construction continued until 1867.

[1] The church hosted choirs assembled by Sir Arthur Sullivan and Gustav Holst; the opera composer Alfred Cellier was organist from 1862 to 1866,[1] playing an organ made by Hill & Son in 1859 (and later enlarged by them).

[8] In 1924 the church appointed the recently retired London County Council architect Charles Canning Winmill (1865-1945),[9] who lived locally at 2 Eliot Place and attended the church,[10] to design All Saints' Parish Hall, which was constructed on land donated by the 6th Earl of Dartmouth in nearby Tranquil Vale and opened in 1928.