Construction of the church began in 1954 and was completed the following year. It was designed by F J Osbourne and was the first new church to be built in Birmingham after the Second World War.

Christian worship on the site began in the canteen hut, by kind permission of Bryant the builders. The first members got the hut ready on Saturday evening, and put it back to its canteen layout at the end of Sunday. The base for the first font (a drainpipe covered in concrete) can be seen at the back of the church.

The new church was consecrated by the Lord Bishop of Birmingham, Leonard Wilson, on 1st November 1955, and visited by Her Majesty Queen Elizabeth II two days later (in pouring rain!).

The architect and writer Niklaus Pevsner described All Saints as a very ugly church. Well, we beg to disagree. It is an impressive and striking design, and there is no mistaking the fact that it is a Christian church. It needs to be seen from inside to appreciate its character.

In June 1993 emergency work on the cupola and tower roof was needed as it was in danger of collapse due to the uprights twisting. The cupola holds a 10 foot high cross and after the work was completed the church tower was 3 feet lower than when it was built.

The church celebrated its 60th birthday in 2015 and is still going strong!