W dniu 10 maja 1983 roku kardynał Franciszek Macharski poświęcił kaplicę i uroczyście erygował nową parafię. 22 sierpnia 1984 rozpoczęto budowę nowego kościoła. Z czterech projektów świątyni, parafianie wybrali do realizacji pracę, której autorami byli Krzysztof Dyga oraz Andrzej Nasfeter.
Budynek nie jest olbrzymi, wkomponowany w zieleń i zbudowany z materiału, z którego postawiono nowohuckie bloki, z cegły. Tak jak wygląda kościół, tak wyglądała Nowa Huta do końca lat 60. XX wieku, kiedy otynkowano nowohuckie bloki. Świątynia ma nowoczesną bryłę z charakterystycznym dachem, który, gdy patrzymy na budynek od frontu, daje niezwykły kształt – drzewo. Wejścia to korzenie i pień a dach to gałęzie, rozłożysta korona. Wnętrze nie jest podzielone na nawy, jak w tradycyjnych świątyniach, ale jest jedną surową ale jasną i przestronną halą. Narożniki kościoła zdobią posągi ewangelistów. Budowę ukończono w 1995 i 11 czerwca tegoż roku kardynał Franciszek Macharski dokonał konsekracji kościoła. W tym samym budynku znajdują się pomieszczenia klasztoru oraz Męskiego Liceum Ogólnokształcącego św. Bernarda oo. Cystersów. Na placu przed kościołem znajdują się pomniki ks. Jerzego Popiełuszki, prasy podziemnej okresu stanu wojennego oraz pomnik 25-lecia Solidarności.