A kereszténység első századaiban a Kálvária-domb melletti völgykatlanban állt egy római anfiteátrum, sőt az újabb kutatások szerint egy fel nem tárt római kori színház van.

Krisztus után 309-ben itt ítélték halálra keresztény hitéért Szent Kvirin sisciai püspököt. Malomkövet kötöttek a nyakába és a megáradt Perintbe dobták.

A korai középkor óta ezen a dombon előbb fa-, majd kőkápolnákat építettek. Ezek azonban az idők folyamán teljesen elpusztultak. 

A jelenlegi templomról - bár, azóta többször átépítették – az 1700-as évektől kezdve vannak írásbeli adatok. Szily János, az első szombathelyi püspök 1780.május 29-i vizitációja szerint 1757-ben az elpusztult ősi kápolna helyén templom épült a hívek adományából.

A templomot évtizedeken át egy-egy remete gondozta. Az első remete, akinek nevét ismerjük: Hilárion testvér. Utódai évtizedekig gondozták a templomot. A Szily-féle vizitáció szerint a kálváriától délre lévő remetelak a város költségén épült. A remeteség intézménye abban az időben egy korabeli szociális kérdést is hivatott volt megoldani.

Bőle András szombathelyi plébános 1802-ben készült jelentésében megemlíti, hogy ebben a kápolnában őrzik a Szent Kereszt hiteles ereklyéjét.

Ugyanő - mint püspök – 1841. június 14-én végzett vizitációja alkalmából feljegyzi, hogy a „főoltár Krisztus keresztje tiszteletére készíttetett”. Azt is leírja, hogy a Kálvária templom „tűrhető állapotban” van. Az épület állaga egyre romlott. Ezért a XX. Század elején Brenner János építész tervei alapján az addigi barokk jelleget neogótikus vonásokkal keverve átalakították, megépítve a két tornyot és az akkor divatos gótikus támpilléreket.

1905.február 11-től kármelita nővérek (sarutlan) vették át templomot István Vilmos püspök idejében és építettek kolostort. A templom belső berendezését új alkotásokkal egészítették ki. Az oltárok, valamint a főoltár nagyfeszülete Lewisch Róbert alkotása. 1910-ben Fichlakker Alajos szombathelyi asztalos készítette a templom ma is meglévő padjait, mindegyikre rávésve a kármeliták címerét.

1905-ben a templomnak két harangja volt. Ezeket 1915-ben elvitték. Néhány év múlva egy kisharangot kaptak ajándékba a nővérek.1932-ben Slezák budapesti harangöntő készített két nagyobb harangot. Az egyiket a második világháborúban beöntötték.

A művészi, kézi faragású Szent Józsefet ábrázoló barokk szobor nagyon régi, amelyet a kármelita nővérek már itt találtak. A Szűzanya szobrát Rómából hozatták. Nagy Szent Teréz, Keresztes Szent János és Lisieux-i Szent Teréz képeit Soós M. Alojzia festette. Az 1981. évi felújításnál ezeket lefestették.

1930-34 között volt komolyabb átépítés. Ekkor készült a szentélyt a hajótól elválasztó boltíves diadalív, amelynek művészi díszítését egy zalaegerszegi református festőművész készítette. Festményét – amely olyan mélyen hatott rá, hogy katolizált – a templom 1981. évi belső felújításakor lefestették.

A famennyezetet a 30-as évek elején Gruber József tervei alapján az Andráskay-Müller cég készítette. A domborművü Keresztút, külön figyelmet érdemel. Gruber Leo bécsi, közismert szobrászművész e remekével felvételizett 1929-ben a budapesti Iparművészeti Főiskolára. A főoltár keresztjének korpusza a Kremzerschmidt iskola alkotása. Az oltár szobrai Münchenben készültek.

A templom őrzi Przudzik József festőművész két alkotását. Ő festette a bejárattól jobbra látható, Lisieux-i Kis Terézt ábrázoló képet, valamint ő restaurálta (jelenleg az oratóriumban található) Krisztus keresztre feszítését ábrázoló XVIII. századi flamand barokk iskolát követő ismeretlen művész festményét.

A gyóntató bejáratánál a házasságtörő asszonyt ábrázoló kerámiagrafika, valamint az északi belső falon látható három címer Pápai Éva művész munkája.

A II. Vatikáni Zsinat szándékának megfelelően 1981-ben került kialakításra a templom új liturgikus tere Rácz Gábor iparművész tervei szerint. Lebontásra került a régi karzat és nagyobb teherbírású épült. A tabernákulum és a papi szék mögötti faliszőnyeget 1984-ben készítette Háger Rita iparművész. 1986-ban készült el a németországi Bautzen város Eule orgonagyárában a 14 regiszteres, 2 manuálos orgona. Ez az ország egyetlen, barokk hangolású (Silbermann II) orgonája. A templom rendkívül jó akusztikája miatt rendszeresen készültek itt hanglemezfelvételek.

1991-ben a templom külseje megújult. Ekkor került kialakításra az új bejárati rész az előtetővel.