Budowę kościoła na Nowej Osadzie rozpatrywano już w poł. XIX w. Na prośbę o użycie kwoty z rozbiórki kościoła św. Katarzyny na remont Kolegiaty KRSW 8 X 1845 wyrażała zgodę, gdyż proponowana budowa kościółka w Nowej Osadzie nie może na teraz przyjść do skutku.
Powstał wg proj. Jerzego Siennickiego w 1938-40 i 1946-51. Pierwsze zebranie Komitetu Budowy Kościoła odbyło się 12 XII 1937. 22 III 1938 dokonano transakcji, za 20.900 zł zakupiono 3682 m2 placu przy ul. Lwowskiej, na którym stał budynek gminy, stróżówka, areszt i budynek gospod. z wozownią, miał to być wcześniej grunt kościelny, a budowę rozpoczęto miesiąc później. W czasie okupacji w nieukończonym - nawa pod dach i wieża 7 m ponad chór (nakrytym) kościele znajdował się magazyn mienia pożydowskiego. Nabożeństwa odprawiano w podziemiach pod prezbiterium zw. Kaplicą betlejemską (potocznie "Betlejemka", bo bardzo uboga). Obsługiwał ją ks. E. Mikołajun. Ołtarz z niej przeniesiono w 1946 na górę.
Kościół poświęcony został 10 XI 1946. 4 V 1947 odbył się pierwszy odpust. W czasie konsekracji 17 IX 1978 zmieniono wezwanie (dotąd p.w. Znalezienia Drzewa Krzyża Św.) od 1 I 1950 jest kościołem parafialnym, a w 1978-94 dekanalnym. Przez długie lata był to surowy, nieotynkowany budynek o prostej "fabrycznej" bryle, jak napisał prof. Kowalczyk. Bynajmniej jednak nie jest przykładem powojennej zgrzebności budowlanej, lecz nakreślonym przed wojną czołowym przykładem funkcjonalizmu w regionalnej architekturze sakralnej. Portyk i ażurowe cebulaste zwieńczenie wieży (38 m) z majolikowym zegarem (mechanizm: Aleksander Mamcarz) projektował Tadeusz Witkowski (1975-78) - przed paroma laty w ramach dokończenia cudzego projektu, wobec zgonu autora, zaprojektowałem i zrealizowałem dla kościoła wieżę. Jest to jednonawowe wnętrze z kasetonowym sufitem oraz prostokątnym prezbiterium i niszą ołtarzową. W bocznym ołtarzu św. Antoniego (poświęcony 1948), autorem figury świętego z drzewa lipowego był Lucjan Pakulski (1946).
Pierwszy ascetyczny wystrój prezbiterium i ołtarz zaprojektował Adam Klimek (był w nim duży krucyfiks, obraz Chrystusa Króla, później obraz MB Nieustającej Pomocy). W l. 60. ściany ozdobiły monogramy chrystusowe i maryjne, a w l. 70-tych znalazły się nowe, oryginalne ołtarze proj. Jarosława Kabat-Sowińskiego z Krakowa, terakotowa posadzka. Ołtarz główny tworzyła jasna, pastelowa mozaika witrażowa przedstawiająca Chrystusa Zmartwychwstałego z otwartym sercem i promienistą aureolą, w duży krzyż wkomponowano tabernakulum (piaskowiec józefowski, Jan Kudełka z Józefowa), na ścianie za ołtarzem napis Adorujemy Cię Chryste i błogosławimy Tobie, żeś przez Krzyż Swój Święty świat odkupić raczył.
T.zw. "szklany ołtarz" znajdował się do 1998 (zły stan techniczny, rozebrany). Powstał nowy, poświęcony 29 XI, obecny marmurowo-miedziany wystrój prezbiterium (proj. Jerzy Nowakowski, Wojciech Kurowski, Andrzej Boj-Wojtowicz - mal., Ewa Jonas Wojtowicz - rzeźb.). Na bocznych ścianach prezbiterium, jako płaskorzeźby przedstawione zostały sceny z życia Pana Jezusa. W 2002 w ołtarzu znalazła się Ostatnia Wieczerza z nadnaturalnymi figurami apostołów i Chrystusem, nie jako jako postać,  lecz ukrytym w Tabernakulum (proj. Maria Gmyz, rzeźby Janusz Szczekan z Hrubieszowa). Nad ołtarzem zawieszono dopełniający motyw zbawienia stary krucyfiks z bocznego ołtarza, prawdopodobnie z dawnego kościoła franciszkańskiego, z "artykułami Wiary" (przedtem w ołtarzu bocznym. konserwowany 1998, Tomasz Dudek). Pod krzyżem umieszczono pochodzący z Uhnowa duży (wys. 3,8 m) obraz Wniebowzięcia NMP (k. XVII w.).
W obu ołtarzach bocznych są miedziane płaskorzeźby. Po lewej (patrząc od wejścia) znajduje się ołtarz maryjny - MB Nieustającej Opieki z zobrazowaniem 15 Tajemnic Różańcowych. Po prawej jest  ołtarz św. Krzyża z przedstawieniem 12 artykułów Wiary, Znajduje się w nim relikwiarz z cząstką Drzewa Krzyża Św. widoczny dla adoracji wiernych. Od 2006 jest też portret bł. bpa Sebastiana Pelczara (mal. Jan Szarlip z Zamościa, fund. spokrewnieni z nim Gujscy z Zamościa).
Godna uwagi była także Droga Krzyżowa miejscowego rzeźbiarza Lucjana Pakulskiego (1948), zastąpioną w 2017 Drogą J. Szczekana, oraz drewniane ławki i konfesjonały wykonane przez szkołę salezjanów w Oświęcimiu (1956-60, proj. Jan Kajzer). Można też zobaczyć tu długi czas jedyny w mieście cykl witraży. Z 1974 pochodzą 3 dzwony (Dzwony kościoła św. Krzyża). W l. 80. we frontonie kościoła powstały płaskorzeźby - kard. Stefana Wyszyńskiego i św. Maksymiliana Kolbego (J. Hycki).
Cmentarz kościelny otrzymał w 1955 granitowe ogrodzenie (20 wagonów, proj. A. Klimek). Na cmentarzu znajduje się Grota Objawień MB z Lourdes (1977) ufundowana przez proboszcza ks. Andrzeja Jabłońskiego i Pomnik Męczeństwa Polaków w II wojnie (osobne hasło: Pomniki), obydwa proj. J. Kabat-Sowińskiego oraz liczne tablice pamiątkowe, m.in. poświęcona pierwszemu proboszczowi ks. Marianowi Giermakowskiemu i na ścianach zewnętrznych poświęcone martyrologii wojennej. Plebania przy kościele wzniesiona w 1952, potem rozbudowywana.

 * Komitet Budowy Kościoła św. Krzyża - Wincenty Służewski, Jan Kowalski, Ludwik Bayer, Jan Marszalec, Maria Kowerska, Wacław Bajkowski, Bolesław Bajankiewicz, Tadeusz Zaremba, Aleksander Jabłoński, Andrzej Dziuba, Jan Koziołek, ks. Franciszek Zawisza (z odezwy, IV 1938)
 * W czasie okupacji sowieckiej zagrożonych rabunkiem 12 żelaznych dł. 12,5 m dźwigarów na strop kościoła uratowano wrzucając przez wybity otwór do środka. Drzwi główne zastawione były nierozebranym jeszcze budynkiem gminy.
 * 1 VII 1945 zorganizowano loterię na budowę kościoła.
 * Poświęcenie (10 XI 1946) ma się odbyć o godz. 11. Punktualnie o 10-tej zaczyna lać jak z cebra. Do kościoła dojść trudno. Obok kościoła błocisko. Z chodnika zrobionego ze żwiru, ani śladu, znalazł się pod wodą. (...) Poświęcenie najpierw  najpierw wewnątrz, a później zewnątrz. Właśnie wtedy padał największy deszcz, a ks. Zawisza z kropidłem zrobionym z ziela  brodził do kolan w błocie.
 * Wg wykazu z 1954 - obok statuy św. Antoniego, zniszczonej bez stylu. była jeszcze statua Serca Jezusowego (zakupiona podczas pielgrzymki w Częstochowie), Matki Boskiej, św. Teresy i św. Józefa.
 * Po zmianie w 1998 ołtarz ambona, lektorium otrzymało marmur ciepły różowy i jasny beżowy, centralna ściana kamień zielony, jako tło do rzeźb z biał marmuru – Pieta, nad nią krzyż przeniesiony z bocznego ołtarz z oryginalną metaloplastyką.
 * Jak odnotowano w historii kościoła - w 1952 podczas nabożeństwa, w obecności księży, 8-letnia dziewczynka zaczęła po raz pierwszy mówić.