Kostel Povýšení sv. Kříže je nejstarším Českolipským kostelem a byl postaven koncem 14. století Českolipskými měšťany v čele s purkmistrem Jindřichem z Vajtmělé a se souhlasem tehdejšího městského faráře rovněž z rodu Vajtmělé a s povolením pana Hynka Berky II. Ze zakládací listiny vyplývá jasný patronát Lipských měšťanů nad tímto kostelem. V r. 1426 kostel i město vyhořely a zdá se, že kostel sv. Kříže byl delší dobu mimo provoz. Kostel byl znovu vysvěcen Litoměřickém proboštem Benešem Valdštejnem r. 1490, který byl současný biskupem v Kaminu v Ponořanech.

V r. 1893 byla vyslovena domněnka, že stavitelem nově postaveného kostela byl Beneš z Loun, známý jako Benedikt Rejt. Dle písemních dokladů teprve r. 1512 převzal pokračování stavby kutnohorský Sv. Barbory a zemřel r. 1530 v Lounech. Kdyby stavěl křížový kostel, musel by být činný jako stavitel celého půl století, ale tomu nelze věřit. Za reformace je o kostelu málo slyšet. Poslední boží tělový průvod z kostela na náměstí byl r. 1573, pak se už v průvodu nechodil, aby ho protestanti nerušili. R. 1592 poprvé v kostele kázal luteránský kazatel. Koncem r. 1622 se podařilo Albrechtu Valdštejna vrátit katolíkům kostel v Lípě.

Hrabě Vilím, majitel Českolipského a zahrádeckého panství, daroval kostelu krásný hlavní oltář, který stojí v kostele dodnes. Až do velkého požáru r. 1787 sloužil kostel jako hřbitovní a po zkáze děkanského kostela se stal kostelem farním. Byl důkladně obnoven v letech 1842, 1845, 1847. V r. 1868 se musel znovu zpevnit dřevěný strop. Při té příležitosti byly odstraněny tehdejší stropní obrazy.

S důkladnou opravou bylo započato Pražským stavitelem svatovítského domu Mockerem v r. 1896. Ten nechal strhnout cihlovou zeť vstupního prostoru, a tak vynikla krása středověké gotiky. Rovněž uvnitř byl stržen starý nehezký balkon a postavena nová kruchta s novými varhanami od pražské firmy Schiffner. Také v presbytáři byl prkenný strop odstraněn a byla vyzděná nová kamenná klenba. Gotická okna dostala barevní skla při zachování původních gotických kružeb na podzim 1897 byly všechny práce skončeny a 19. září 1897 byl kostel litoměřickým biskupem Schoblem znovu vysvěcen.

V presbytáři jsou po obou stranách postaveny chórový lavice, které pocházejí z bývalého benediktického klášterního kostela sv. Mikuláše v Praze na Starém Městě. Jsou vyzdobeny kopiemi Albrechta Durera a Jana van Rycla.

V r. 1937 byla provedená velká obnova vnitřku kostela. Tuto úpravu svěřili malíři Rudolfu Gortlerovi Nového Boru II-Arnultovic. Ten vyzdobil 96 polí dřevěného stropu eucharistickými symboly. V tomto roce bylo rovněž do kostela zavedeno elektrické osvětlení.

Kostel je majetkem katolické církve i v poslední době byl využíván výhradně pro pohřby.

V roce 2002 Pravoslavná církevní obec si kostel zapůjčila svoje bohoslužebné účely.