Około roku 1200 biskup krakowski Pełka (Fulco) ufundował w Krakowie kościół pw. Św. Krzyża. Pierwotna budowla była murowana z ciosów piaskowca. Nie wiadomo, gdzie dokładnie była usytuowana ta późnoromańska świątynia, być może stała na miejscu obecnego kościoła.
W 1244 r. biskup Prandota przeniósł duchaków z Prądnika Białego do Krakowa (gdzie ufundował i uposażył nowy szpital i klasztor) i oddał im – już parafialny wówczas – kościół Św. Krzyża, wiążąc nierozerwalnie jego dzieje na następne pięć i pół wieku z zakonem i krakowskim szpitalem Ducha Świętego.
Parafia świętokrzyska jest czwartą w Krakowie pod względem czasu jej utworzenia. W dokumencie z 1327 r. biskup Jan tak opisał jej zasięg: wchodząc do miasta Krakowa bramą Floryańską, idąc od tej bramy ulicą z lewej strony aż do murów miasta koło domu braci Mogilskich podobnież po lewej stronie połowa tych ulic z wszystkimi mieszkańcami na nich przeznaczamy do parafii św. Krzyża.1
W XIV w. została zbudowana nowa, gotycka świątynia Św. Krzyża. W tym czasie powstał w kompleksie zabudowań klasztorno-szpitalnych również kościółek pw. Ducha Świętego.
W 1528 r. miał miejsce wielki pożar północno-wschodniej części Krakowa, który strawił oba kościoły, całe archiwum, szpital i klasztor. Zniszczenia były ogromne. W kościele Św. Krzyża runęło sklepienie prezbiterium, sklepienie nawy zostało uszkodzone, wypaliło się wnętrze świątyni, bezpowrotnie odeszły do przeszłości Sakramentarium, wnęka na Oleje Święte i Grób Wielkanocny. W latach 1530-33 z inicjatywy prepozyta Stanisława Teplara udało się naprawić kościół, który potem rekonsekrowano.
W XVII w. kościół mocno podupadł. W 1684 r. dzięki zapisowi biskupa Andrzeja Trzebickiego zdołano go odnowić, o czym świadczy dokument znaleziony w gałce wieżowej. W roku 1722 potrzebna była kolejna naprawa kościoła, gdyż spadła wówczas z wieży wspomniana gałka.
W 1783 r. uległa kasacji polska prowincja duchaków, a kościół i opiekę nad parafią powierzono od 1788 r. księżom diecezjalnych.
Punktem zwrotnym w dziejach świątyni było wyburzenie w latach 1890-92 średniowiecznych zabudowań poklasztornych. Dostrzeżono wtedy bardzo zły stan techniczny kościoła. Rada Miasta podjęła decyzję o jego gruntownej restauracji, której dokonano w latach 1896-98 nakładem Kasy Oszczędności miasta Krakowa. Pracami kierowali architekci Tadeusz Stryjeński i Zygmunt Hendel. Poczynione prace miały na celu przywrócenie budowli dawnej stricte gotyckiej formy (zburzenie kaplicy Przemienienia Pańskiego i przybudówki przy północnej ścianie nawy, odbudowanie klatek schodowych na wieżę i ambonę, wybicie zamurowanego okna we wschodniej ścianie prezbiterium, usunięcie barokowego portalu znad wejścia). Obniżono wówczas o półtora metra teren wokół kościoła, odsłonięto XVI-wieczne malowidła ścienne, odnowiono wnętrze. Choć renowacja ta była dość nieudolna (np. przemalowania zamiast konserwacji), pomogła zachować tę perłę krakowskiego gotyku do naszych czasów.
Drobniejsze konserwacje odbywały się w latach 1930, 1954, 1974, 1983. Ważną jest ta z lat 1958-73, nazwana II fazą odnawiania polichromii, kiedy to usunięto część XIX-wiecznych przemalowań, eksponując oryginalne renesansowe freski.
Po stu latach od ostatniego większego remontu kościół znajdował się znów w stanie zagrożenia. W 1993 r. powołano do życia Fundację Ratowania Kościoła Św. Krzyża w Krakowie. Dzięki jej staraniom zapoczątkowano połączoną z badaniami renowację kościoła. Na ich podstawie udało się ustalić m. in. czas powstania obecnej świątyni. Odrestaurowano elewację, tynki, malowidła ścienne i wszystkie elementy wyposażenia kościoła. Kompleksowe prace konserwatorsko-remontowe trwały do roku 2007. W latach 2001-2003 miał miejsce kapitalny remont organów.
1 K. Bąkowski, Kościół ś. Krzyża w Krakowie, Kraków, nakładem Tow. Miłośników Historyi i Zabytków Krakowa, 1904, str. 8.
Plebania jest najstarszym budynkiem mieszkalnym Krakowa.