Nejstarší farní kostel v Dubé byl zasvěcen sv. apoštolům Petru a Pavlu a stál na nynějším hřbitově u Českolipské ulice. Druhý farní kostel byl postaven v Dubé před rokem 1408 (u nynějšího rybníka) a byl původně zasvěcen sv. Kateřině. V r. 1792 vyhořel, byl znovu postaven a r. 1722 rozšířen. Zasvěcen byl pak Panně Marii Nanebevzaté. Zde byli pohřbíváni páni z Berků a Buttlerů. V r. 1792 byl tento kostel i hřbitov kolem něho zrušen, zachoval se pouze obraz z hlavního oltáře Nanebevzetí Panny Marie malovaný 1729 Richterem a nalézající se nyní v novém kostele nad Mariánským oltářem.

Současný kostel Nalezení sv. Kříže

Základní kámen k třetímu farnímu kostelu byl položen na svátek Nalezení sv. Kříže roku 1744. Byl postaven v italském slohu stavitelem Anselmo Luragem, zcela nákladem hraběte Františka Karla Rudolfa z Swerts - Sporcka. Kostel je 47 m dlouhý, 22 m široký a 21 m uvnitř vysoký. Má dvě věže, které byly ozdobeny lucernovými báněmi, ty však shořely při velkém požáru města roku 1845. Obraz na hlavním oltáři i na vedlejších oltářích sv. Jana Nepomuckého a Panny Marie Bolestné byly namalovány roku 1755 neznámým malířem, který se na zadní straně obrazů podepsal pouze šifrou ,,F.B.“. Z roku 1810 pocházejí obrazy křížové cesty, které daroval Antonín Ungermann. Z roku 1834 pochází obraz sv. Antonína z Padovy, malovaný akademickým malířem Eduardem Svobodou. 1869 byly darovány kostelu obrazy Neposkvrněného početí Panny Marie, sv. Aloise a Ježíše Krista na hoře Olivetské, které jsou malovány akademickým malířem Steffenem z České Lípy. Roku 1788 byly rozšířeny varhany, skříň z nich je zachována až do dnešní doby v původní podobě, starý stroj však byl nahrazen novým v roce 1894, který zhotovila firma Rejna a Černý v Praze. Před rokem 1896 byl postaven nový Mariánský oltář naproti kazatelně a opatřen sochou Neposkvrněného Početí zhotovenou panem Zambachem z Vídně. Socha Božského Srdce Páně na oltáři Bolestné Matky Boží byla zhotovena v umělecké škole v Mnichově r. 1926.

1. prosince 1942 byl zdejší farní kostel povýšen biskupem Aloisem Weberem na děkanský kostel.
9. května 1945 utrpěl kostel velkými otřesy při bombardováni města.
V letech 1985-1991 pod vedením duchovního správce P. Josefa Bělohlava proběhla kompletní generální oprava celého kostela.