Dzieje parafii sięgają 1952 roku. Karol Wojtyła od początku wspierał działalność miejscowego proboszcza i walkę mieszkańców o własny kościół. Władze komunistyczne nie zezwalały na powstanie świątyni we wzorcowej socjalistycznej dzielnicy Krakowa, jakim była Nowa Huta. W 1960 roku nakazano usunięcie krzyża z placu budowy na osiedlu Teatralnym. W jego obronie wystąpili wierni, doszło do zamieszek. W 1969 roku arcybiskup kardynał Karol Wojtyła wmurował kamień węgielny pochodzący z Bazyliki świętego Piotra na Watykanie, a w 1977 roku osobiście konsekrował kościół, pełniący również funkcję sanktuarium Matki Bożej Fatimskiej.

Kościół zbudowano w latach 1967–1977 według projektu Wojciecha Pietrzyka. Dach budowli upodabnia go do arki i stojącej w Ronchamp kaplicy Notre Dame duHaut, czyli Matki Bożej na Górze projektu Le Corbusiera. Nad świątynią góruje krzyż-maszt wysokości 70 metrów. Budynek o powierzchni 1800 metrów kwadratowych mieści około 6000 wiernych. We wnętrzu znajduje się ołtarz z marmuru karraryjskiego w kształcie otwartej dłoni i tabernakulum odlane z brązu w kształcie powstającego kosmosu z „kamieniem księżycowym”, darem kardynała Karola Wojtyły, pochodzącym od załogi statku Apollo 11, choć badania podważają jego autentyczność. Figurę Chrystusa Ukrzyżowanego wykonał profesor Bronisław Chromy, a obraz Matki Bożej Królowej Polski to kopia obrazu ze Zbaraża. Drogę krzyżową w latach 1980–1983 namalował malarz Mariusz Lipiński. Darem katolików z Portugalii jest umieszczona w grocie figura Matki Bożej Fatimskiej, koronowana w 1992 roku. Pod ołtarzem znajduje się grota Matki Bożej, pod nawą Kaplica Pojednania z drewnianymi Pietami Polskimi i rzeźbą świętego Maksymiliana Kolbego, dziełami Antoniego Rząsy oraz figura Matki Bożej Pancernej, wykonana z kul wydobytych z ran żołnierzy, walczących pod Monte Cassino.