Budowę obiektu w stylu neoromańskim rozpoczęto w 1860 r., frontem do ówczesnej ul. Dzikiej (obecnie ul. Sienkiewicza 38), od wylania fundamentów, ale jej przebieg opóźniały problemy finansowe. W kontynuowaniu inwestycji pomógł przemysłowiec Karol Scheibler, przekazując 50 tys. rubli, jak również ofiarowując cztery figury ewangelistów, zdobiące wieżę, i 31-głosowe organy. Właściwa budowa świątyni według projektu Franciszka Tournelle’a rozpoczęła się w 1872 r. i trwała trzy lata. Pierwotnie obiekt został poświęcony 2 listopada 1875 r. jako kościół św. Jakuba, ale finalnie konsekrowano parafię pw. Podwyższenia Świętego Krzyża.
Karol Scheibler i Edward Herbst
Świątynia jest trzynawowa, zbudowana na planie krzyża w układzie bazylikowym. Na wieży znajdują trzy dzwony i sygnaturka. Architekturę wnętrza zaprojektował Konstanty Wojciechowski. Wewnątrz znajduje się sześć ołtarzy. Główny to dar Karola Scheiblera. Ołtarz boczny w lewej nawie ufundował Edward Herbst. Podczas II wojny światowej kościół był dostępny wyłącznie dla Niemców.
W 2021 r. parafię objęli bracia dominikanie z klasztoru bł. Piotra Frassatiego. Przy kościele znajduje się pomnik poświęcony ofiarom stanu wojennego, a także popiersie ks. Stefana Miecznikowskiego.
