Parafia p.w. Podwyższenia Krzyża Świętego powstała z podziału istniejącej dotychczas w Nowej Dębie jednej parafii p.w. Matki Bożej Królowej Polski (Dekret L. 1011-85 z dnia 18 czerwca 1985 r. wydany i podpisany przez bpa Ignacego Tokarczuka). Ośrodek kultu Bożego stanowił będący wówczas w budowie nowy kościół. Dzieje tej parafii jak i kościoła są ściśle powiązane z historią całego miasta. Od czasów powojennych w Nowej Dębie istniała nagląca potrzeba wybudowania kościoła. Miasto bowiem stawało się znaczącym ośrodkiem przemysłowym i liczba jego mieszkańców szybko wzrastała. W tym okresie Nowa Dęba była punktem filialnym parafii Majdan Królewski. Staraniem ówczesnego proboszcza ks. Stępnia, utworzono tymczasową kaplicę w budynku wyznaczonym przez Dyrekcję Zakładów Metalowych. W 1951 r. Dyrekcja wymówiła lokal i kaplicę zamknięto. W tej sytuacji liturgię zaczęto sprawować w prowizorycznie ustawionej szopie na terenie dzielnicy Dęba (obecne miejsce kościoła Matki Bożej Królowej Polski) i rozpoczęto budowę drewnianego kościółka. Ponieważ całe przedsięwzięcie było bez stosownych pozwoleń władz, nie obeszło się bez represji (m.in. Władysław Pyryt i Józef Serafin zostali zwolnieni z pracy). Od 1957 r. proboszczem parafii Nowa Dęba był ks. Henryk Łagocki. On też w łączności z parafianami wielokrotnie występował do władz miejskich i wojewódzkich o pozwolenie na budowę kościoła. Dopiero w 1977 r. takie pozwolenie otrzymał, ale rozpoczęcie budowy było blokowane, gdyż nie uregulowano sprawy zatwierdzenia parafii i osoby proboszcza przez wydział wyznań. Temat ten miał swoje miejsce w postulatach NSZZ Solidarność Nowa Dęba wobec władz miejskich i wojewódzkich w r. 1980. Do starań o pozwolenie na rozpoczęcie budowy doszła sprawa nowej lokalizacji. Uzyskano teren tzw. "górkę". Architekturę kościoła opracował doc. dr Aleksander Bühm, konstrukcję opracował mgr inż. Bogusław Brągiel obydwaj są pracownikami naukowymi Politechniki Krakowskiej. Budowla w rzucie poziomym przedstawia liść dębu, natomiast przestrzennie nawiązuje do tzw. stylu namiotowego (duży dwuspadowy dach intensywnie wznosi się ku górze). W pracach budowlanych rozpoczętych w lipcu 1982 r. pod przewodnictwem ks. Henryka Łagockiego i kontynuowanych przez ks. Eugeniusza Nycza szczególnie wyróżnili się członkowie komitetu budowy i zespół specjalnych zadań. Obejmując całość toku budowy należy podkreślić udział i zangażowanie całej wspólnoty parafialnej, wielu parafian przebywających poza krajem. Zasadnicze prace zakończono w październiku 1990 r. Budowla zawiera dwa poziomy po około 950 m2 każdy, pierwszy jako miejsce kultu, drugi dolny o charakterze wielofunkcyjnym. Kościół jest pokryty blachą miedzianą, wytynkowany wewnątrz i zewnętrz. Parafia posiada akta parafialne od 1985 r.