St. Marys as we now know it was built during the mid nineteenth century, work started in 1860 and the consecration service was held on 11th August, 1862. Several changes have taken place since the completion date, the most significant being the adding of the Tower.
Wythall or Wythworth as it was previously known is mentioned in the Domesday Book, but the first actual information available detailing a church in Wythall was around 1330. Wythworth Chapel is actually marked on the oldest existing road map of England, the Gough Map. Wythworth was then on the main route from Droitwich to Coventry. Travellers would proceed along what is now known as Radford Lane, Hill Lane, Chapel Lane and Station Road. Various other maps detail Wythworth Chapel. In 1576, a map mentions Wytho Chapell, in 1577 Wythe Chap, in 1677 Wytho ChaI and in 1763 Withorn Chapel. These curious names are perhaps ways of abbreviating Wythworth or possibly show the beginning of a lazy pronunciation.
The history of Wythall Chapel during the period preceding the building of the present church is somewhat obscure. We know that during the 17th century the Chapel was in very bad state of repair. Later documentation of 1714 and 1737 reported the roof of Wythall Chapel is out of repair. However, in 1777, the Chapel was rebuilt.
The new Chapel was a small brick building, tiled roof with a wooden bell turret at the West end. The internal dimensions measured 51 10 inches x 22 8. The floors were paved quarries and the wall neatly coloured. Seven windows allowed light into the main part of the building with additional windows in the gallery. The Chapel was entered by a plain door on the South side. There were 29 oak pews, one reserved for the Mynor family. The Communion table and Pulpit were made from oak. The Gallery was reserved for the choir and school children.
This building remained almost unchanged until 1854 when it became apparent that it was the wish of the people of the community for a larger and more worthy place of worship.
A committee was appointed to oversee the building. It was to be financed by wealthy land owners together with grants from the Church Buildings Society and the Church Extension Society. The builder was Mr. I. Clulee of Kings Norton.