Powstanie kombinatu metalurgicznego i miasta Nowa Huta pod Krakowem zostało postanowione przez rząd PRL w dniu 17 maja 1947 roku. Projekt kombinatu był radziecki, ale domy (bloki) planowali polscy inżynierowie. Mieli powiedziane, że w Nowej Hucie nie ma miejsca dla nowego kościoła, bo to miasto miało być socjalistyczne, czyli bez Boga.
Ludzie, którzy tu przyjechali pracować mieszkali początkowo w barakach. Wielu z nich rzeczywiście zatracało wiarę i moralność, ale wielu chciało zachować wiarę wyniesioną, w swoim sercu, z domu rodzinnego. Ci drudzy szukali drogi do kościoła. W okolicy był klasztor Ojców Cystersów i kościół w Czyżynach. Wieś Bieńczyce i okoliczne wioski należały do parafii w Raciborowicach i w Pleszowie. Nie było do nich żadnej drogi z Nowej Huty. Ludzie przychodzili modlić się do małej kaplicy przy ochronce dla dzieci prowadzonej przez Siostry Służebniczki z Dębicy. Tu w tej kaplicy, już w roku 1950, na nabożeństwie 40-godzinnym, głosił kazania ks. Karol Wojtyła, wikariusz od św. Floriana z Krakowa. W tej to kaplicy odprawiano Msze św. i sprawowano nabożeństwa przez kapłanów z Krakowa i mnichów z Mogiły. W dniu 15 czerwca 1952 r., ks. abp Eugeniusz Baziak eryguje parafię Najświętszego Serca Pana Jezusa w Bieńczycach. Parafia liczyła wtedy 3000 mieszkańców. Pierwszym proboszczem - administratorem zostaje ks. Stanisław Kościelny. W pracy duszpasterskiej pomagał ks. Zbigniew Mońko, w spowiedzi pomagali benedyktyni z Tyńca i ks. Karol Wojtyła. Od samego początku istnienia nowej parafii rozpoczęto starania o pozwolenie na budowę kościoła w Nowej Hucie. Słano z parafii i Kurii Metropolitalnej pisma do wszelkich możliwych urzędów prosząc o pozwolenie na budowę kościoła. Zbierano podpisy, jeździły delegacje z parafii, słali prośby biskupi z różnych diecezji na świecie. Wszystko pozostawało bez odzewu, albo władze państwowe dawały twardą odpowiedź, że w Nowej Hucie kościoła nie będzie. Kapłani i wierni nie ustawali w staraniach. Po otrzymaniu sakry biskupiej włączył się w walkę o kościół w Nowej Hucie ks. bp Karol Wojtyła.
Po zmianach jakie przyniósł październik 1956 roku pojawiła się realna nadzieja na uzyskanie pozwolenia na budowę kościoła w Nowej Hucie. W listopadzie 1956 delegacja parafian z Bieńczyc dotarła do Władysława Gomułki. Zapewnił on, że partia nie ma nic przeciwko budowie kościoła w Nowej Hucie, a szczegóły rozwiąże Urząd ds. Wyznań. Faktycznie, jeszcze w listopadzie 1956 uzyskano pozwolenie na budowę kościoła i ustalono jego lokalizację - os. Teatralne. Zawiązał się komitet budowy kościoła. Zbierano pieniądze, kupowano materiały budowlane. Była wielka radość! W dniu 17 marca 1957 roku ks. Abp Eugeniusz Baziak poświęcił plac pod budowę kościoła i ustawiono tam krzyż na znak, że tu będzie kościół, a ziemia jest poświęcona Panu Bogu. Nowa Huta liczyła wtedy 80 000 osób.
Pierwszy projekt kościoła z dwoma wieżami wykonał inż. arch. Zbigniew Solway. Komuniści nie kryli swojej złej woli. Zażądali odwołania ks. Stanisława Kościelnego. Nie podobała im się jego kapłańska gorliwość. Ta ofiara została złożona, ks. Kościelny opuścił Nową Hutę 16 lutego 1959 roku. Nie o to jednak komunistom chodziło. W dniu 10 czerwca 1959 roku cofnięto pozwolenie, zabrano z konta bankowego pieniądze na kościół, zabrano materiały budowlane i na miejscu gdzie miał stanąć kościół zaczęto budować szkołę w ramach „1000 szkół na 1000 lecie”.
Nowy proboszcz, ks. Mieczysław Satora i wierni nadal kołatali u władz o cofnięcie krzywdzącej decyzji. Władza komunistyczna odpowiedziała decyzją o usunięciu krzyża z placu przeznaczonego pod kościół. 27 kwietnia 1960 roku robotnicy ze spychaczem przybyli na plac, aby usunąć krzyż. Rozpoczyna się jedyna w swoim rodzaju "walka o krzyż Chrystusowy w Nowej Hucie". Przejeżdża dużo milicji, bo gromadzą się liczni wierni, którzy czynnie bronią krzyża. Już w południe są pobici i ranni. Po pierwszej zmianie przychodzą robotnicy z kombinatu. Komuniści gromadzą dużo milicji i wojska z KBW. Około 20.00 cała Nowa Huta zostaje pozbawiona elektryczności, zaczęto strzelać, używać armatek wodnych i gazu łzawiącego. Rozpoczęły się masowe aresztowania. Wielu rannych ukrywa się w blokach. Komuniści plac kościelny zabrali. Katolikom zostały łzy i jeszcze większa wiara, bo wzmocniona ofiarą krwi i cierpienia.
W obronie ludzi i sprawy wielką rolę odegrał ks. bp Karol Wojtyła. Nie ustawano w staraniach o pozwolenie na budowę kościoła. Komuniści znowu żądają zmiany proboszcza. Ks. Satora odchodzi do pracy w Kurii, a parafią kieruje, bez nominacji, ks. Zbigniew Mońko i księża wikarzy: Ks. Stanisław Gałuszka, ks. Eugeniusz Sukiennik.
W roku 1964 arcybiskupem metropolitą krakowskim zostaje Karol Wojtyła. Szuka odpowiedniego kapłana, którego komuniści zatwierdzą na proboszcza w Nowej Hucie. Wreszcie proboszczem zostaje w czerwcu 1965 roku ks. Józef Gorzelany, dotychczasowy proboszcz z Filipowic. Gdy przybył do Bieńczyc, przy kaplicy sióstr były już od lat drewniane salki katechetyczne i prowizoryczny ołtarz, była powiększona kaplica polowa. Księża mieszkali "u ludzi" w wynajętych mieszkaniach.
W październiku 1965 roku parafia otrzymuje nową lokalizację pod kościół – w miejsce dotychczasowej kaplicy. Kościół postanowiono wznieść jako wotum na 1000 lecie chrztu Polski i nowemu kościołowi i parafii nadano jako patronkę Maryję Królową Polski. Papież Paweł VI ofiaruje dla nowego kościoła kamień węgielny z bazyliki Konstantyna Wielkiego z czwartego wieku i dość sporą sumę pieniędzy. 14 października 1967 roku ks. abp Karol Wojtyła wykopał pierwsze grudy ziemi pod nowy kościół w Nowej Hucie.
Budowa kościoła trwała dziesięć lat. Dlaczego tak długo? Projektantem kościoła został inż. arch. Władysław Pietrzyk, konstruktorem prof. Jan Grabacki. To dobry zespół, ale władze zatwierdzały projekt budowy kościoła "po kawałku", zawsze trzeba było czekać na kolejne decyzje, materiały budowlane były "na przydział", a takiego przydziału parafie nie miały. Materiały, trzeba było „załatwiać” nawet za granicą, za dolary i na podstawionych ludzi. To była wielka męka budowy. Wspaniałymi okazali się ludzie z całej olbrzymiej parafii, z Polski, z Europy i z całego świata. Ten kościół to owoc solidarności w wierze w Jezusa Chrystusa Zbawiciela świata. Budujących podnosił na duchu ks. kardynał Wojtyła, który często odprawiał tu "pod gołym niebem" Msze, a zwłaszcza pasterki. Wreszcie, 15 maja 1977 roku, ks. Kardynał Wojtyła dokonał poświęcenia tej wyjątkowej świątyni i postanowił podzielić tego "giganta" na cztery parafie - rejony i nakazał budować nowe kościoły w Nowej Hucie. Za rok został wybrany papieżem. Jego dzieło podjął nowy arcybiskup - ks. kardynał Franciszek Macharski, który w przedmowie do książki Jadwigi Gieruli "Arka Pana", tak pisze w roku 2002: "W roku obecnym mija 50 lat od utworzenia parafii Matki Bożej Królowej Polski w Nowej Hucie. To parafia szczególna - jej dzieje, a zwłaszcza ćwierć wieku [1952 - 1977] zmagania o budowę są jakąś syntezą historii ludzi wierzących i Kościoła w Polsce po II wojnie światowej".
Parafia Królowej Polski przystąpiła do realizacji podziału na mniejsze parafie. Powołano tzw. proboszczów rejonów: rejon I - Królowej Polski, proboszczem tego rejonu, który miał kościół i który służył pozostałym "parafiom rejonowym", został ks. Franciszek Skupień. Proboszczami parafii - rejonu II, Najświętszego Serca Pana Jezusa byli kolejno: ks. Janusz Bielański i ks. Jan Gwizdoń, ale nie zbudowali kościoła dla swojej parafii. Proboszczem dla rejonu III był ks. Jan Zając, a po nim ks. Jan Bielański, który zbudował kościół św. Brata Alberta i został pierwszym proboszczem tej parafii. Proboszczem dla rejonu IV był najpierw ks. Leon Baran, następnie ks. Stanisław Podziorny, który zbudował kościół św. Józefa i został pierwszym proboszczem tej parafii. Jeszcze przez kilka lat ks. Józef Gorzelany był "prawnym" proboszczem całej parafii, ale duszpasterstwo prowadzili proboszczowie rejonów. W roku 1986 ks. Gorzelany przestaje być proboszczem, jego funkcje do roku 1988 pełni ks. Franciszek Skupień. W roku 1988 proboszczem parafii Królowej Polski zostaje ks. Karol Jarosz, a proboszczem parafii Najświętszego Serca Pana Jezusa jest nadal ks. Jan Gwizdoń.
Mają do dyspozycji jeden kościół. W roku 1986 odchodzi ks. Gwizdoń, a proboszczem obydwu parafii zostaje ks. Jarosz. W roku 1995 w miejsce ks. Jarosza proboszczem zostaje ks. Edward Baniak.
Ważnym wydarzeniem w życiu parafii była koronacja figury Matki Bożej Fatimskiej papieską koroną. Dokonało się to 13 września 1992 roku. Koronacji dokonał arcybiskup Stanisław Nowak z Częstochowy. Nie mógł w niej uczestniczyć kardynał Franciszek Macharski, gdyż w tym czasie przechodził operację z powodu choroby nowotworowej. Kult Matki Bożej Fatimskiej zapoczątkował w parafii bieńczyckiej ks. Józef Gorzelany. Po dziś dzień jest on niezwykle żywy. Arka Pana jest fatimskimi sanktuarium.
Skala problemów w tej podwójnej parafii: pracowało tu 17 kapłanów, było osiem szkół podstawowych, osiem średnich i trzynaście przedszkoli. Pierwsza komunia odbywała się przez cztery niedziele, po dwie szkoły w jeden dzień, do bierzmowania w jednym roczniku było ponad 500 młodzieży. Spowiedź przed świętami trwała cały miesiąc. Parafie te liczyły razem 42 000 ludzi. Proszę sobie wyobrazić skalę problemów gdy parafia liczyła 92 000 wiernych. Po kilku latach udaje się ks. Baniakowi zbudować mały kościół Najświętszego Serca Pana Jezusa przy Krzyżu Nowohuckim, na os. Teatralnym i w roku 2001 powstaje tu nowa parafia. Jej proboszczem zostaje ks. Stanisław Puzyniak. Dla tego II Rejonu powstaje też w roku 1999 drugi kościół budowany przez księży pallotynów, pod wezwaniem Matki Bożej Pocieszenia. Budową i parafią kieruje jej pierwszy proboszcz, ks. Józef Gwozdowski SAC. W ten sposób wypełniony został testament Jana Pawła II.
Wydzielenie z parafii Matki Bożej Królowej Polski parafii Najświętszego Serca Jezusowego i Matki Bożej pocieszenia zakończyło proces normalizowania duszpasterstwa w tej części Nowej Huty, która stanowiła parafię bieńczycką – parafię Arki Pana.