W założeniach władz PRL-u Nowa Huta miała być najbardziej socjalistycznym miastem przemysłowym w Polsce, bez miejsca dla Boga. Miejscowi katolicy musieli chodzić na msze do oddalonego o 5 km kościoła w Raciborowicach, ale nie osłabli w swej wierze i nie rezygnowali z tradycji. W ciągu kilkunastu lat liczba wiernych wzrosła do ponad 90 tys. W 1957 r. władze wydały pozwolenie na utworzenie nowej parafii, ale dwa lata później decyzję cofnęły. Walka o świątynię dla Nowej Huty trwała aż do 1965 r., kiedy to dzięki wstawiennictwu kardynała Karola Wojtyły uzyskano zgodę na jej budowę.
W 1967 r. rozpoczęto prace budowlane. Pierwszą łopatę wbił w ziemię kardynał Wojtyła. Autorem projektu był Wojciech Pietrzyk, który wzorował się na słynnej kaplicy Notre Dame du Haut w Ronchamp. Świątynia przy ul. Obrońców Krzyża 1 przypomina kształtem wielką łódź zwieńczoną masztem - krzyżem, dlatego o tym kościele Matki Bożej Królowej Polski mówi się najczęściej po prostu Arka Pana. Podobnie jak całą dzielnicę, budowali go własnymi rękami mieszkańcy - bez użycia ciężkiego sprzętu i nowoczesnych technologii, gdyż żadna z państwowych firm nie chciała pomóc. Elewację zdobi około 2 mln kamieni otoczaków, przywiezionych przez parafian z okolicznych rzek i strumieni.
Wystrój wnętrza jest uważany za jeden z najlepszych projektów w kraju. W tabernakulum umieszczono kamień pochodzący z księżyca - dar amerykańskich kosmonautów dla papieża Pawła VI, który sprezentował go potem nowohuckiej parafii. Katolicy z Holandii i Belgii przekazali 8 dzwonów, obecnie noszących imiona osób związanych z Arką Pana. W przedsionku podziemnej kaplicy, zwanej Kaplicą Pojednania, stoi figurka Matki Boskiej z Dzieciątkiem wykonana z kul, które zostały wyjęte z ran żołnierzy walczących o klasztor na Monte Cassino. Męczeństwo Polaków podczas II wojny światowej symbolizują również Piety Polskie - rzeźby zaprojektowane przez podhalańskiego twórcę A. Rząsę.