The present church was constructed by George Dance the Younger in 1767, replacing an earlier church built some time in the early 12th century on a bastion of the old Roman wall. It became renowned for its hermits, who lived in cells in the church. All Hallows escaped destruction in the Great Fire of London in 1666 due to its position under the wall, but subsequently fell into dereliction.
Dance rebuilt the church when he was only 24 years old. He had recently returned from Italy where he had conducted detailed studies of Classical buildings. The new All Hallows took its inspiration from the Classical world and was remarkably simple in form, with no aisles; its interior consists solely of a barrel-vaultednave with a half-dome apse at the far end, with decoration deriving from the ancient Temple of Venus and Rome in the city of Rome. Attached Ionic columns support a frieze, rather than the usual entablature. The exterior is plain and of brick, except for the stone- faced tower above the porch at the west end.
All Hallows was damaged during the Second World War but was restored in the early 1960s. It is a guild church associated with the Worshipful Company of Carpenters, which has held its annual elections in the church for over 600 years. Until 1994, it was the headquarters of the Council for the Care of Churches. The church was designated a Grade I listed building on 4 January 1950.
It is now the home of the urban youth charity XLP, and City Gates Church, a congregation with roots in the British New Church Movement.