An iron mission church was opened in 1875, and a parish was assigned out of Holy Trinity Church, Bordesley.

The foundation stone for the permanent church on Cooksey Road was laid on 15 September 1882.

Dempster and the contractor was Barnsley and Sons, Rylands Street North, Birmingham.

All Saints’ was badly damaged in an air raid during the Second World War and demolished shortly afterwards.

The new parish decided to retain only St Aidan's Church building, and in 1998 this was renamed All Saints.