Do końca lat 70., nowohucka parafia liczyła ponad 100 tys. wiernych. Pierwszym proboszczem (administratorem) był ks. Stanisław Kościelny, drugim zaś ks. Mieczysław Satora.
Proboszczem parafii Matki Bożej Królowej Polski, którego postać wpisała się mocno w historię Nowej Huty, był ks. Józef Gorzelany. To on uczestniczył nie tylko w budowie kościoła Arka Pana, ale był także w 1981 r., współtwórcą pierwszego i największego polskiego Hospicjum im św. Łazarza w Nowej Hucie. Imieniem tego proboszcza nazwano po jego śmierci Rondo Kocmyrzowskie w Nowej Hucie.
O 1995 r. proboszczem parafii jest ks. Edward Baniak. Pytany, jak czuje się jako „sternik” Arki Pana, odpowiada z uśmiechem: - Zawsze lubiłem wodę i rzekę, bo jako dziecko mieszkałem nad Rabą. Nad morze też bardzo lubiłem jeździć. Święcenia otrzymał w 1972 r., a na motto swojego życia wybrał słowa „Bądź wola Twoja”. Ks. Baniak jest dumny, że w jego parafii jest bardzo dużo pobożnych ludzi - działają tutaj 32 wspólnoty. A marzeniem Księdza Proboszcza jest znalezienie drogi do serc i umysłów ludzi młodych.

Walka o krzyż

Pierwsi chrześcijanie umierali na arenach cyrkowych za wiarę. W swoich wspomnieniach ks. Gorzelany pisał: „W Nowej Hucie jak za pierwszych wieków chrześcijaństwa ludzie musieli ciężko wywalczyć prawo do wiary i praktyk religijnych w godziwych warunkach. Dokonali tego zupełnie przeciętni ludzie, niewolni od wielu wad i słabości”.
Niezwykle poruszający jest opis walk o 8-metrowy krzyż w Nowej Hucie z 27 kwietnia 1960 r. Mieszkańcy Nowej Huty nie dopuścili do usunięcia krzyża z placu budowy. Użyto wówczas przeciwko nim oddziałów ZOMO i ostrej amunicji. Na pamiątkę tych krwawych zamieszek ulicę, na której stał krzyż, nazwano ul. Obrońców Krzyża.
Najstarsi parafianie pamiętają także wydarzenia ze stanu wojennego. Wspominają jak członkowie ORMO strzelali do figury Matki Bożej w Bieńczycach i wspominają cud z 1982 r., gdy żadna z petard, które upadły do Jej stóp, nie wybuchła.

Kościół, który nie stoi na ziemi

Po długich negocjacjach z władzami, 14 października 1967 r. rozpoczęto budowę świątyni według projektu Wojciecha Pietrzyka. Prace były przeprowadzane bez udziału maszyn, bowiem tylko przedsiębiorstwa państwowe dysponowały sprzętem technicznym: stal zbrojeniową podawano ręcznie, a płynny beton wożono na taczkach! Tak w latach 1968 -80 budowano wszystkie kościoły.
Kamień węgielny podarował papież Paweł VI, a pierwsze uderzenia kilofa wykonał kard. Karol Wojtyła. Świątynia o nietypowym kształcie miała przypominać łódź albo arkę Noego. Od kształtu świątyni (ważącej kilkaset ton!) powstała jej nazwa: Arka Pana. Sam budynek kościoła porównuje się nie tylko do arki, ale i do kaplicy w Ronchamp, projektu Le Corbusiera.
Na ścianach kościoła znajdują się kamienie - otoczaki- symbol żywego Kościoła. Te kamienie nowohuccy parafianie w czasie dziesięcioletniej budowy zbierali własnymi rękami podczas urlopów m.in.: w Popradzie i Dunajcu.
Kiedy rozpoczęto budowę świątyni, natrafiono ponoć na skład amunicji. Wówczas saperzy wydobyli z ziemi 5 023 sztuk pocisków. Istnieje hipoteza, że kościół stanął na olbrzymim podziemnym jeziorze, znajdującym się na głębokości 600 m.
Niewyczerpaną skarbnicą wiedzy o kościele jest przewodnik Mariana Kardaszewskiego pt.: „Arka Pana”.

Kamień nie z tej Ziemi

W świątyni znajduje się tabernakulum z brązu. Ma ono kształt kuli ziemskiej i przypomina koło sterowe arki. Niektórzy mówią, że na drzwiczkach tabernakulum umieszczono rutyl przywieziony przez amerykańskich kosmonautów podczas misji „Apollo 11”. Kosmonauci podarowali księżycowe kamienie Ojcu Świętemu, a Paweł VI przekazał jeden z nich ks. Gorzelanemu. Drugi taki kamyczek znajduje się w muzeum w Watykanie, za kuloodporną szybą.
We wnętrzu świątyni warto zwrócić uwagę na rzeźbę Chrystusa w agonii. Wykonał ją, na podstawie rysunku polskiego więźnia obozu koncentracyjnego, prof. Bronisław Chromy. Nosi ona tytuł: „Z życia do życia”.

Pancerni i spiżowi bohaterowie Nowej Huty

W kościele Arka Pana, w kaplicy Pojednania (wejście od ul. Obrońców Krzyża), jest kamienna ściana. To imitacja muru oświęcimskiego z obozową drogą krzyżową (z samych krzyżyków) i napisem w języku hebrajskim „Shalom”- Pokój. Na tej ścianie znajduje się wnęka, w której stoi figurka Matki Bożej Pancernej. Waży ona 10 kg i mierzy 60 cm wysokości.
Pancerna postać jest zespawana z odłamków granatów, min, bomb kul armatnich i karabinowych, którymi ranieni byli polscy żołnierze, gdy zdobywali Monte Cassino w maju 1944 r. I właśnie te odłamki, wyciągnięte z ciał rannych przez chirurgów, stanowią materiał, z którego jest zrobiona figurka Matki Bożej trzymająca Dzieciątko.
Ciekawa jest historia pozyskiwania tego „materiału”. Otóż polscy kombatanci, chcąc wspomóc duchowo mieszkańców Nowej Huty (kiedy ci toczyli walkę o kościół z władzami), złożyli te cenne „10 kilogramów” u polskiego oficera, który wykonał tę figurkę i ofiarował na ręce kard. Karola Wojtyły w 1975 r. Obok kościoła znajduje się również osiem dzwonów ofiarowanych przez katolików holenderskich. Od godz. 6 do 22, o każdej pełnej godzinie wydzwaniają one znane pieśni. Te dzwony noszą imiona osób, które szczególnie zasłużyły się dla historii Nowej Huty i budowy kościoła Arka Pana. Warto je poznać: „Karol” (Wojtyła), „Józef” (Gorzelany - pierwszy proboszcz kościoła i twórca nowohuckiego hospicjum,), „Bruno” (Gryksa, fundator dzwonu), „Lonny” (Gloser, współorganizatorka pomocy materialnej dla budowy kościoła z Austrii. „Stanisław” (Biela, zdobywał materiały do budowy), „Wojciech” (Pietrzyk - architekt), „Jan” (Norek - kierownik prac), „Antoni” (Pietraszek - majster). Dodatkowo przed kościołem na tablicach są zamieszczone nazwiska mieszkańców wsi Bieńczyce, którzy zginęli podczas II wojny światowej.

Do końca lat 70. nowohucka parafia liczyła ponad 100 tys. parafian (kościół mógł pomieścić 6 tys. osób). Posługę pełniło 17 księży. Dziś parafia została podzielona na kilka nowych.

Szczątki dawnego krzyża (oryginału, o który toczyły się walki), znajdują się w kotwicy kościoła Arka Pana. Niektórzy zaś twierdzą, że drobne części wziął ze sobą do Rzymu Jan Paweł II.
Najstarszym zabytkiem w kościele jest zawieszony na dwóch stalowych linach po prawej stronie ołtarza obraz Matki Bożiej pochodzący z 1600 r., znajdujący się niegdyś w kościele w Zbarażu.