Ši bažnyčia primena pranciškonų kankinių istoriją, prasidėjusią dar XIV a.
Pasak legendos, 1333 m. pagonys nužudė 14 pranciškonų, kuriuos į Vilnių iš Podolės buvo pakvietęs Petras Goštautas ir apgyvendinęs savo namuose toje vietoje, kur vėliau buvo vyskupų rūmai. Septynis iš jų prikalė prie kryžių ant Plikosios kalvos (dabar Trijų kryžių kalno) ir paskui įmetė į Vilnelę. Kitiems septyniems nukirto galvas vietoje.
Grįžęs Goštautas surinko kankinių kūnus ir gražiai palaidojo toje vietoje, kur šiandien stovi šv. Kryžiaus bažnyčia, ir ant jų kapo pastatė kryžių. Vėliau čia buvo pastatyta koplyčia, kuri 1524 m. sudegė.
1543 m. bažnyčią pastatė Vilniaus vysk. Paulius Algimantas Alšėniškis. Jis tų pačių metų rašte mini, kad vyskupų sode pranciškonų kankinių garbei stovi paminklas — kolona su kryžiumi, kuris per 1531 m. gaisrą likęs nesunaikintas. Tas kryžius laikomas stebuklingu ir po II Pasaulinio karo buvo perneštas į šv. Onos bažnyčią.
Prie kankinių kulto prisidėjo ir Vilniaus kanauninko Jono Andruševičiaus, vėliau tapusio Kijevo vyskupu, stebuklingas pagijimas per tų kankinių užtarimą. Jis 1545 m., atsidėkodamas kankiniams, jų garbei parašė lotynišką himną, iškalė jį marmuro lentoje ir pakabino prie šv. Kryžiaus koplyčios durų.
Vilniaus vysk. Abraomas Vainius 1635 m. pastatė barokinę mūrinę šv. Kryžiaus bažnyčią ir ligoninę, pavesdamas tarnystę vienuoliams bonifratrams, kurie dar globojo prie bažnyčios esančius negalią turėjusių kunigų namus. 1843 m. rusai vienuolius išvarė.
1905 m. bažnyčią restauravo jos administratorius Valatka. 1915 m. bažnyčioje meldėsi visa Vilniaus lietuvių Vytauto Didžiojo gimnazija, taip pat jų mokytojai Aleksandras Stulginskis, Antanas Smetona, Dr. Gylys, Pijus Grajauskas, Matas Bagdonas, gimnazijos steigėjas — prof. Mykolas Biržiška ir kt. 1921 m. kovo mėn. šioje šventovėje buvo paminėta Gudijos nepriklausomybės paskelbimo trejų metų sukaktis. Tada kun. A. Stankevičius pasakė gudų kalba pamokslą.
Vysk. J. Matulaitis 1924 m. bažnyčią grąžino vienuoliams. Vėliau ji buvo atnaujinta. 1932 m. arkivyskupas R. Jalbžykovskis bažnyčią konsekravo Dievo Motinos ir šv. Kryžiaus titulu. Iki 1940 m. prie bažnyčios buvo ligoninė ir senelių prieglauda.
Tęsdami carų tradicijas, rusai, po II Pasaulinio karo okupavę Lietuvą, vienuolyną panaikino, o bažnyčią pavertė pradžioje kraštotyros muziejumi (1945 — 1956 m.), vėliau muzikos sale. 1992 m. birželio 3 d. bažnyčia grąžinta Vilniaus arkivyskupijai. 1995 m. atšventinant bažnyčią buvo grąžintas ir čia kabantis Švč. Marijos paveikslas, kuris iki tol glaudėsi šv. Onos bažnyčios kairiajame altoriuje.
Šiame paveiksle Marija pavaizduota iki pusės, ant kairės rankos laikanti Kūdikį, dešinę ranką laiko ant kairiosios, jos žvilgsnis nukreiptas tiesiai. Jėzus kairę ranką padėjęs ant kelių, o dešine laimina. Pasukęs galvą į Mariją, žiūri į priekį. Figūros uždengtos sidabriniu aptaisu, atviri tik veidai, rankos ir Jėzaus pėdos. Aplink Marijos galvą aureolė iš 12 žvaigždžių, sujungtų brūkšniukais. Jėzaus aureolė panaši į saulę, iš kurios eina tankūs ir smulkūs spinduliai. Ant abiejų galvų yra karūnos, papuoštos brangiais akmenimis. Virš Marijos karūnos — viena didelė žvaigždė, ant kaklo karoliai. Paveikslas tapytas aliejiniais dažais ant medžio lentų. Aplink paveikslo figūras prikabinta daugiau nei 200 votų, kuriomis žmonės išraiškia padėką už gautas malones. Dalis jų ant paveikslo netilpo, tad kabinti aplink.
Įdomu, jog šalia bažnyčios trykšta šaltinis, anksčiau žmonės galėjo pasisemti vandens po bažnyčia esančiame šulinėlyje, kuris yra išlikęs iki šių dienų.
Vilniaus šv. Kryžiaus bažnyčios rektoriai nuo 1995 m.
1995.12.08-1998.09.02 Kun. Juozapas Minderis
1998.09.02-2010.07.13 Kun. Juozapas Minderis
2010.07.13-2014.06.03 Kun. Ričardas Doveika
2014.06.03-2016.03.01 kun. Virginijus Česnulevičius (arkikatedros administratorius)
2016.03.01-2019.01.31 Kun. Paulius Gil
2019.01.31- iki šiol Kun. J. Farelas Peternal
