W 1973 r. wydano pozwolenie na wybudowanie punktu katechetycznego i tymczasowej kaplicy, ale wewnątrz osiedla. Na terenie nowego kościelnego placu znalazła się Zielona Budka. Dziś nieco zapomniana stoi nadal w swoim miejscu i oglądać ją można na terenie kościelnym od strony pętli tramwajowej. Trzy lata później – 22 kwietnia 1976 r. uzyskano pozwolenie na budowę nowego kościoła. Ksiądz Kurzeja nie doczekał poświęcenia nowej świątyni, zmarł 15 sierpnia 1976 r. w wieku 39 lat, w wyniku skrzepu w płucach i zatoru w mózgu. Pochowany został tymczasowo na cmentarzu Grębałowskim, a jego pogrzeb stał się jedną z większych manifestacji mieszkańców Nowej Huty. Proces beatyfikacyjny księdza Józefa Kurzei rozpoczął się 4 maja 2005 r. i od tej chwili przysługuje mu tytuł Sługi Bożego.
Pierwszą mszę św. w głównym kościele odprawiono w Wielkanoc 3 kwietnia 1983 r.
Budowla Kościół wybudowano w latach 1976–1983 według projektu architekta Józefa Dutkiewicza. Budowla składa się z dwóch poziomów oraz połączonej z kościołem plebanii i 10 sal katechetycznych.
Ściany kościoła i plebanii wykonane są z ciętych płyt z białego kamienia pińczowskiego, a schody do kościoła wyłożone są czerwonym piaskowcem szydłowieckim.