Somborska rimokatolička crkvena opština obratila se, još 1818. godine, ugarskom Kraljevskom namesničkom veću, sa molbom da joj se besplatno dodeli plac za izgradnju nove katoličke crkve u Somboru, pošto je crkva Svetog Trojstva postala pretesna za velik broj vernika. Gradski senat se saglasio sa ovom molbom, ali se nakon toga zastalo, pa su vernici 1826. g. ponovo predložili da započnu radovi na izgradnji nove crkve. Gradske vlasti su 1828. g. taj predlog prihvatile i imenovale komisiju koja je trebalo da odredi mesto na kome će crkva biti podignuta, što je i učinjeno do 1833. godine, kada je na gradskom Vašarištu, sa severoistočne strane od zdanja Županije, određeno zemljište za zidanje nove crkve. Ipak, na početak gradnje čekalo se još duže od četvrt veka.
Godine 1859. ponovo je oživljena inicijativa za početak gradnje nove rimokatoličke crkve (agilnošću je prednjačio Lorenco Lovro Falcione, koji je predložio da se za izgradnju nove crkve preusmere prihodi od zakupa radnji u crkvenom posedu, kao i da se počne sa prikupljanjem priloga vernika). Početkom oktobra 1860. g. svečano je otpočela gradnja nove crkve, nakon mise i priziva Svetog Duha, a ovdašnji župnik Erne Kele, u pratnji mnoštva građana i đaka, prvi je počeo sa kopanjem njenih temelja. Još iste godine podignuti su zidovi crkve do visine od 120 cm. U narednom vremenu, usled nekoliko nerodnih i plavnih godina, te nedostatka novca, gradnja crkve je bila znatno usporena, zbog čega su Somborci 1865. g. od Kaločke nadbiskupije tražili zajam od 10.000 forinti. Godine 1875. inženjer Đula Partoš je procenio da je za završetak izgradnje crkve potrebno između 150 i 180 hiljada forinti, pa je Odbor za izgradnju odlučio da se, zbog nedostatka sredstava, privremeno obustavi podizanje crkve. Stanje se nije nabolje promenilo ni tokom narednih godina, pa je 1880. g. urednik somborskog lista „Bačka“, koji je izlazio na mađarskom jeziku, pomalo cinično predlagao da se izgrađeno poruši i građevinski materijal da se rasproda jer je u proteklih petnaestak godina u podizanje crkve uloženo oko 40.000 forinti, a izgradnja nije daleko odmakla. Zagrebački novinar, koji je 1885. g. posetio Sombor, zapisao je: U stranu od županije videsmo nedovršenu veliku katoličku crkvu – skoro se ruše zidovi… Grade je preko dvadeset godina, pa sad tako stoje zidine – nemaju ljudi novaca.
Kada je 1894. g. Sombor posetio kaločki nadbiskup Đerđ Časka, preko tri stotine Somboraca (mahom ovdašnjih Bunjevaca), samonicijativno i bez podrške gradskih vlasti i crkvene opštine, došli su nadbiskupu sa molbom da podizanje crkve bude nastavljeno. Njihovi zahtevi su urodili plodom, pa je ubrzo, na predlog nadbiskupa Časke, osnovan Odbor za nastavak gradnje, čiji su članovi bili neki od uglednijih somborskih rimokatolika (dr Žigmund Turski – somborski gradski “fiškal”, Vince Žufa, Imre Fraj, Andrija Pekanović, Peter Veselovski, Karlo Majer i Antal Žubori), pa je, tokom narednih osam godina, nova crkva, konačno, stavljena pod krov (već 1895. g. u Sombor je stigao nadbiskupski inženjer i slikar Feliks Daberto, koji je trebalo da pregleda radove i izvrši pripreme za slikanje crkvenog svoda).
Mada je, neko vreme, stojala bez dva monumentalna tornja, izgradnja crkve potpuno je završena uz državnu pomoć, a krstovi na crkvenim tornjevima svečano su postavljeni i osvećeni u julu 1902. godine, po velikom pljusku i nevremenu. Nadbiskup Časka, kome pripadaju najveće zasluge za dovršetak ove crkve, proglašen je za počasnog građanina Sombora.
Sagrađena kao trobrodna bazilika u stili neoromantizma, nova rimokatolička crkva u Somboru bila je posvećena svetom mađarskom kralju Ištvanu (Stefanu, Stipanu ili Stjepanu), prvom krunisanom hrišćanskom vladaru Mađara i utemeljitelju srednjovekovne mađarske države, koji je vladao od 997. do 1038. godine. Crkva je svečano osvećena 20. avgusta 1904. godine, na praznik svog zaštitnika, a velikoj svečanosti prisustvovalo je više hiljada katoličkih vernika iz Sombora i okoline.
Drvene skulpture u unutrašnjosti crkve izradila je tirolska radionica Ferdinanda Štuflesera, koji je vešto izbegao kitnjastu patetiku ravnajući se prema uzorima rane renesanse, Rafaela i Direra. Glavni oltar je darovao kaločki nadbiskup Đerđ Časka, porodica Pekanović je poklonila oltar svete Ane, oltar svetog Antuna darovala je udova bogatog somborskog žitnog trgovca Antuna Fernbaha, oltar Blažene Djevice Marije bio je dar somborskih salašara, a imućni somborski vernici darovali su još nekoliko crkvenih kipova i vitraže.
Kada je crkva sagrađena, u gradu je, početkom 1904. godine, postavljeno pitanje da li da je povere svetovnom sveštenstvu ili nekom monaškom redu. Gradske vlasti su se protivile zamisli da se osnuje druga crkvena župa, a kaločki nadbiskup Đerđ Časka, koji je, ujedno, bio i najveći priložnik za izgradnju crkve, predložio da pastoral u novoj crkvi preuzme karmelićanski monaški red, što je, uprkos prvobitnom protivljenju većine somborskih odbornika, na kraju i prihvaćeno (karmelićani su rimokatolički monaški red koji potiče od pustinjaka sa brda Karmel u Palestini, a u Evropi se javlja od 13. veka). Tada je odlučeno da se pored crkve sagradi i Karmelićanski samostan.
Za razliku od crkve koja je građena pune 42 godine, manastirska zgrada je sagrađena veoma brzo. Njen kamen temeljac bio je postavljen 4. jula 1904. godine, a već 14. maja 1905. g. zdanje je blagosiljano. Kao i crkva, i karmelićanski samostan je sagrađen u stilu neoromantizma, a nalazio se neposredno uz južnu stranu crkve, sa kojom je činio jedinstvenu arhitektonsku celinu. Velik i lepo uređen manastirski vrt bio je ograđen zidom. Tokom Prvog svetskog rata (1915) u manastirskoj zgradi kraće vreme je bila smeštena vojska i vojna zarazna bolnica, a nakon Drugog svetskog rata nove vlasti su oduzele karmelićanima veći deo manastirskog zdanja i pretvorile ga u školski prostor, dok su karmelićani bili smešteni u uskom dograđenom delu manastirske zgrade. Zdanje je potpuno vraćeno karmelićanskom redu 1962. godine. Unutrašnjost samostana obnovljena je 1995/96. godine, a tokom 2002/03. g. obnovljeni su krov i fasada.
U Salcburgu su tokom 1925. godine, u fabrici orgulja „Cecilija“ Hansa Maurahera (prema projektu Jožefa Gejera, profesora liturgike i organologa na konzervatorijumu u Budimpešti), izgrađene crkvene orgulje Sv. Male Terezije za somborsku Karmelićansku crkvu, nadaleko znane po svojoj veličini i lepoti. Nekadašnji direktor somborske gimnazije, ugledni ovdašnji intelektualac dr Ede Margalić, svedoči u svojoj autobiografiji kako je, mada već u godinama, pristao da se, na sva tri jezika ovdašnjih vernika, obrati šezdesetorici imućnih somborskih domaćina katoličke veroispovesti, i da ih pozove na prilaganje do potrebnog iznosa od 400.000 dinara za kupovinu i sklapanje orgulja. Margalić piše da su prilozi davani brzo i revnosno, potrebna suma je prikupljena, i naširoko i nadaleko čuvene orgulje već godinama trube u slavu Božju. Orgulje su najveće na prostoru Vojvodine (imaju tri manuala, 43 registra i oko 3.400 svirala; sistem rada je pneumatski). Blagosiljane su 14. februara 1926. g. u prisustvu bačkog biskupa Lajče Budanovića, predsednika Narodne skupštine Kraljevine SHS Marka Trifkovića, velikog župana Bačke županije Milivoja Petrovića i mnogobrojnih vernika iz Sombora i okoline.
Krajem 1936. g. opravljeni su krstovi i gromobrani na vrhu crkvenih tornjeva. Detaljna obnova krovne kosntrukcije Karmelićanske crkve započela je u proleće 2016. godine.
U crkvi, u oltaru Sv. Križa, nalaze se danas mošti oca Gerarda (Grge) Tome Stantića (1876-1956), karmelićana koji je u samostan došao odmah po njegovom osnivanju 1904. godine i koji je, svojim predanim redovničkim i pastoralnim životom, stekao među vernicima izuzetan ugled i poštovanje (1985. g. započet je proces njegove beatifikacije).
Kameni krst na nekadašnjem vašarištu ispred Županije, koji se danas nalazi u parku ispred samostana, podigla je 1829. g. Ana, supruga somborskog graditelja Franca Gfelera, sa natpisom na nemačkom jeziku. Krst se prvobitno nalazio kraj samog crkvenog zida i bio je okrenut prema zapadu, a posle je izmešten u neposrednu blizinu, u park, ali je okrenut prema severu.
Milan Stepanović
