Den nye bys indbyggertal forvandlede sig på 50 år fra århundredeskiftets 4000 indbyggere til fyrrenes 20.000. Hermed var det klart, at behovet og ønskerne for flere kirker indenfor byområdet var voksende og efter en længere debat, blev man enige om i nærmeste fremtid, at bygge to kirker i byens vestre og østre del.En indsamling blandt befolkningen resulterede i et beløb på 400.000 kr. På gården "Fredhøjs" marker var Herning Andelsboligforening i gang med opførelsen af bebyggelsen "Fredhøj" med mere end 275 lejemål. Herning Kommune købte en del af gårdens jord og skænkede det til kirkebyggeriet.

Da kommunen samtidig manglede et nyt vandtårn i denne bydel og efter at planerne om et kombineret vand- og kirketårn blev godkendt i kirkeministeriet, kunne tårnet opføres i 1950.

Byggeriet af Sct. Johanneskirken startede i 1953 og kirken var klar til indvielse i november 1955. Kirken er opført i røde mursten, arkitekten E. Packness tegnede kirken og den er opført og færdiggjort af arkitekt Søren Jensen, Herning. 

Grundplanen er et langhus med sakristi i øst og en forhal i vest. Bygningen er præget af mange forskellige stilarter, senere tilbygninger fra 1977 og 1991 indeholder kontorer og møderum og konfirmandlokaler. Med disse nye bygninger fremtræder kirken nu som et firelænget anlæg.

Kirkens udsmykning præges af en glasmosaik i østgavlen over alteret, orglets usædvanlige placering over sakristiet bag alteret er bestemt af kirkens arkitekt. Tårnet prydes af fire urskiver og 
fire ørne - evangelisten Johannes´ mærke.