Landsbyen Herning havde oprindeligt en romansk granitkvaderkirke, der lå lidt nordvest for bebyggelsen. Efter byens fremvækst blev kirken betragtet som for lille og for afsidesliggende. Den blev nedrevet i 1887, og i 1889 blev den erstattet af den nuværende Herning Kirke tegnet af Claudius August Wiinholt.
Den store, røde teglstenskirke ved byens torv er opført i romansk stil med tårn og spir. Den oprindelige alterudsmykning af farvede fliser, tegnet af H.B. Storck og modelleret og bemalet af Thorvald Bindesbøll, står nu i sakristiet, for i 1916 blev den erstattet af en altertavle med maleri fra 1914 af Joakim Skovgaard, Jesus i synagogen, og en ramme skåret af Niels Larsen Stevns. I 1916 udsmykkede Viggo Madsen felterne på prædikestolen fra 1889 med bibelske scener, og han malede også de store, musicerende engle på indgangsvæggen. I 1954 fik byens valgmenighed sin egen, enkle langhuskirke i tegl, og i 2004 forsynede Arne Haugen Sørensen kirken med altermaleri af nadveren og tre vinduesmalerier.
