It is not known when the church was built. It is recorded in the Domesday Book, but as Tettenhall had a tiny population at the time, the church was probably quite small. In 1950 most of the building, except for the tower, was completely destroyed by fire. After the fire, when the church was almost completely rebuilt, no trace could be found of any Saxon stonework.

Like St. Peter's Church in Wolverhampton, Tettenhall Church was a collegiate church, run by a dean and a college of prebendaries. The Dean was also Lord of the Manor of Tettenhall Clericorum, the northern part of the village including Barnhurst, Bilbrook, and Aldersley. There were five prebends, one for each of the following areas: Tettenhall, Perton, Wrottesley, Pendeford, and Codsall.

After the fire on 2nd February, 1950, all that remained intact was the 14th century tower with its peal of eight bells, and the Victorian porch. In the early 1950s a new nave, chancel and vestry were designed by Bernard Miller, an architect who had been closely associated with the Liverpool School of Architecture. The church was rebuilt in modern Gothic style, and consecrated on April 16th 1955.