La actual iglesia victoriana se construyó en el sitio de una predecesora del siglo XIII, que se documentó en 1263. La iglesia se amplió en la época medieval y la estructura resultante consistió de una nave y un presbiterio elevado, naves laterales del norte y sur y una torre noroeste con chapitel.
En 1547, aunque no se conserva ningún registro para indicar cuándo aparece el primer reloj en Birmingham, durante este año, los Comisionados del Rey informan que la Guilda de la Santa Cruz es responsable «de mantener el reloj y el quimo» a un costo de cuatro chelines y cuatro peniques al año en la iglesia de San Martín. La siguiente mención registrada de un reloj es en 1613. Los primeros fabricantes de relojes conocidos en la ciudad llegaron en 1667 desde Londres.
En 1690, los capilleros «vistieron la iglesia de ladrillo». Todo fue revestido en ladrillo con la excepción del chapitel.[2]
John Cheshire reconstruyó 40 pies del chapitel en 1781, que fue reforzado por un huso de hierro que subía por su centro hasta una longitud de 105 pies. Se aseguró a las paredes laterales a cada diez pies mediante tirantes. En 1801, varios metros de la parte superior del chapitel fueron reemplazados después de que se descubrió que habían decaído. Las puntas de los cuatro pináculos que rodean el chapitel principal también fueron reconstruidas. En 1808, el chapitel había sido golpeado por un rayo tres veces.[2]
En 1853, Philip Charles Hardwick retiró la cubierta de ladrillo de la torre, quien agregó el púlpito al aire libre. La iglesia también contenía un órgano, cuya reedificación había sido realizada por John Snetzler. Sin embargo, se descubrió que los tubos no eran efectivos debido a su proximidad con el techo y las paredes de la iglesia.[2]
En 1873, la iglesia fue demolida y reconstruida por el arquitecto Julius Alfred Chatwin, conservando la torre y el chapitel anteriores. Durante la demolición, se descubrieron pinturas murales medievales y decoraciones en el presbiterio, incluida una que muestra a la beneficencia de San Martín que divide su manto con un mendigo. También se encontraron dos vigas pintadas detrás del techo de escayola.
El exterior está construido en piedra de Grinshill. El interior es de piedra arenisca con un techo de madera abierto,[4] que muestra la influencia del gran hammerbeam roof del Westminster Hall. Las vigas están decoradas con tracería fina y terminan en grandes esculturas de ángeles. El techo pesa 93 toneladas, abarca 22 pies (6,7 m) sobre la nave de 100 pies (30,4 m) y tiene una altura de 60 pies (18,2 m).[5]
El transepto sur tiene una ventana diseñada por Edward Burne-Jones, y realizada por William Morris en 1875. Esta ventana se bajó por seguridad el día antes de que una bomba de la Segunda Guerra Mundial cayera junto a la iglesia el 10 de abril de 1941, destruyendo todas las ventanas restantes. La ventana oeste es una copia de 1954 de la ventana de Henry Hardman de 1875 destruida en el Blitz.[5]
La ventana este de Hardman, representa escenas del final de la vida de Cristo: la última cena, la entrada a Jerusalén, la limpieza del templo, la agonía en Getsemaní y el beso de la traición.
La ventana oeste de Hardman, representa a Cristo en Majestad con los arcángeles, ángeles, y santos.