La primera piedra del primer edificio de la iglesia fue colocada el 17 de mayo de 1852 por la Sra. Taylor, [2] y la construcción comenzó con los diseños de James Lyndon Pedley. El edificio se abrió al culto cuando fue consagrado el martes 17 de mayo de 1853 [3] por el obispo de Worcester, y su construcción costó 5.500 libras esterlinas. Se asignó una parroquia de la iglesia de San Nicolás, Kings Norton en 1853. [4]
De la parroquia de St Paul, se tomaron tierras para formar otras nuevas iglesias en Birmingham, incluyendo St Thomas in the Moors, Balsall Heath en 1884, St Patrick's Church, Bordesley en 1900, St Agatha's Church, Sparkbrook en 1902 y St Barnabas 'Church, Balsall Heath en 1905.
En la década de 1970, la congregación no podía costear el mantenimiento y, junto con la Iglesia Reforma Unida de la Iglesia de Cristo, [5] construyó un nuevo edificio. En 1979 se inició la construcción de una nueva iglesia por los arquitectos Hinton Brown Langstone [6] y fue consagrada en 1980 por el obispo Hugh Montefiore.
La iglesia contenía un órgano de Henry Willis que se instaló en 1880. Se puede encontrar una especificación del órgano en el Registro Nacional de Órganos de Tubos. [7] Cuando la iglesia cerró en 1979, el órgano se vendió a la iglesia de St George, Battery Point, Hobart, Tasmania .