Na mestu sedanje župnijske cerkve, ki je posvečena oglejskim mučencem (Kancijan, Kancijanila, Kancij in Prot), je vsaj že v 2. polovici 6. stoletja stala zgodnjekrščanska cerkev, ki je imela na severni strani prizidano osmerokotno krstilnico (ostanki te so vidni pod tlakom severno od cerkve). Ladja zgodnjekrščanske cerkve je bila široka približno 12 m (od severnega roba klopi v severni ladji do južnega roba klopi v južni ladji), dolžina, ki sicer ni bila ugotovljiva, pa je bila – glede na primerjave – okrog 24 m. Na severni strani sta bila od ladji dva stranska prostora, na temeljih severnega zidu teh dveh prostorov stoji severni zid današnje cerkve. Na zahodni strani je bil v cerkev vključen vhodni prostor (narteks), v katerem so po takratnih predpisih prisostvovali bogoslužju tisti, ki še niso bili krščeni.

Okrog te prve cerkve je od konca 7. stol. začelo nastajati obsežno grobišče, ki je bilo v uporabi vse do 1798. Zgodnjekrščanska cerkev je bila porušena ali opuščena v 1. polovici 9. stoletja, preživela pa je osmerokotna krstilnica, ki s tem dokazuje nepretrgan obstoj krščanstva v Kranju iz pozne antike v zgodnji srednji vek. Zgodnjesrednjeveška cerkev je nastala deloma na temeljih zgodnjekrščanske vsaj že ob koncu 9. ali v začetku 10. stol. Njena podoba nam podrobneje ni znana, ker dosedanje raziskave niso segle pod cerkvene klopi.

Malo pred letom 1405 je službo župnika v Kranju nastopil Koloman de Manswörth, vpliven in kulturno razgledan član nižjega plemstva. Pomembna je njegova povezava s Hermanom II. Celjskim, ki je imel v letih od 1400 do 1421 v zakupu mesto Kranj. Koloman je leta 1413 začel graditi novo cerkev, najprej prezbiterij, ki je bil v skladu s takratnimi potrebami zasnovan kot dolgi kor. Tak prezbiterij je ob glavnih bogoslužjih omogočil sodelovanje vseh duhovnikov in pevcev. Ob severni in južni strani prezbiterija sta bila zgrajena še zakristija in stopniščni stolpič, o čemer pričajo ostanki zazidanih portalov v ostenju prezbiterija. Stranska prostora ob prezbiteriju sta dobila današnjo obliko šele v 18. in 19. stol. Zasnova gradnje prezbiterija s pomočjo enakostraničnega trikotnika, nekateri arhitekturni detajli (oblikovanje reber) in številni kamnoseški znaki povezujejo gradnjo kranjskega prezbiterija s t.i. celjsko delavnico – stavbno delavnico, ki je za celjske grofe zgradila samostan Pleterje, knežji dvor v Celju in cerkev sv. Danijela v Celju.

Spor župnika Kolomana s kranjskimi meščani, ki je nastal zaradi gradnje novega župnišča na mestnem zemljišču, je povzročil, da se je gradnja ladijskega dela cerkve in zvonika nadaljevala šele po letu 1426 – vendar po prvotni zasnovi celote. Ta faza gradnje je vključevala tudi obokanje zahodne empore (v nadstropju zvonika), izdelavo glavnega portala z reliefom Oljske gore, služnike in konzole ob stenah ladje ter štiri stebre s kapiteli. V severni in južni cerkveni steni sta bila tudi dva stranska portala, ki sta bila ob regotizaciji cerkve leta 1877 prenesena na sedanje mesto. Ladijski prostor je sicer zasnovan pravokotno, vendar njegov zahodni del zasedata zvonik in zahodna empora, tako da je ladja pravzaprav pravilen kvadrat, kar še poudarja razporeditev 4 stebrov. Celota je zasnovana v razmerju zlatega reza (prezbiterij : ladja = ladja : celota). Vgradnja zvonika v ladijski prostor in posamezni arhitekturni detajli (zlasti figuralne konzole, kapiteli in relief v luneti glavnega portala, oblikovanje glavnega portala) kažejo sorodnosti s cerkvijo na Ptujski gori. Na te povezave opozarjajo tudi kamnoseški znaki. Ptujskogorska stavbna in kiparska delavnica, katere sledove lahko iščemo v kranjski župnijski cerkvi, pa je posrednik vplivov velikega stavbenika Petra Parlerja in njegovih sinov, ki so med drugim gradili tudi katedralo v Pragi. Posamezni motivi na kapitelih kranjskih stebrov nakazujejo povezave tudi z gradbiščem dunajske stolnice, kjer je v letih 1420 do 1431 kot kamnosek in stavbenik izpričan tudi neki Hanns Krainer ("Kranjski Janez").

Po dogradnji zvonika in ladijskih sten z nastavki za oboke je zaradi smrti župnika Kolomana gradnja cerkve za nekaj časa zastala. Leta 1434 se že omenja zvonik, torej je ta gradbena faza morala biti takrat že zaključena. Ladja je bila do nadaljevanja gradnje verjetno ravno krita. V listini iz leta 1452 (za časa župnika Matije Koferja) pa se omenja, da sta mestni svet in mestni sodnik dovolila, da se za obokanje cerkve in za cerkveno opremo uporabijo sredstva cerkvenih bratovščin. Ladijski obok je moral biti zaključen pred letom 1460, ko so nastale freske angelov muzikantov v osrednji obočni zvezdi. Obok, ki ga tvorijo osmerokrake zvezde, prekriva devet kvadratnih obočnih polj, pri čemer je višina obokov v stranskih in glavni ladji enaka. S tem je prvič na slovenskem ozemlju uveljavljen dosleden dvoranski tip cerkve. Namesto starejše gotske vzdolžne usmeritve ladje in višinskega zagona slopov, ki se nadaljujejo v obok, imamo opraviti s centralizirano, renesančno občuteno enotno prostornino, na kateri počiva svod, katerega rebra se začenjajo šele od kapitelov navzgor. Prostorski koncept, kakršnega je uveljavila kranjska župnijska cerkev, je deloma rezultat domačega arhitekturnega razvoja, ki pa je sprejemal vplive z Bavarske (npr. Marijina cerkev v Nürnbergu), predvsem pa s Češke (npr. cerkev sv. Trojice na Kutni Hori).

Bogat kamnoseški okras na sklepnikih kranjskega oboka je vsebinsko povezan z nekdanjo razporeditvijo oltarjev v ladji. Pod sklepniki z upodobitvijo Matere Božje in posameznih svetnikov (sv. Janez Krstnik, sv. Nikolaj, sv. Štefan…) so namreč stali oltarji, posvečeni tem zavetnikom. Iz odprtine v centralnem oboku, ki jo obdajajo trtni listi, je visel Križani. Skozi to odprtino so ob prazniku vnebovhoda dvignili kip vstalega Kristusa, ob binkoštih pa spuščali kip goloba kot simbol Sv. Duha. Zanimiva je tudi vsebina oboka pod korom, kjer so okrog centralnega sklepnika s podobo Matere Božje z Jezusom razporejeni sklepniki z upodobitvami sv. Treh kraljev, na četrtem sklepniku pa je v značilni noši upodobljen donator, morda mestni sodnik. Obok opozarja na povezavo s Kölnom, kjer so hranili relikvije sv. Treh kraljev in kamor so Kranjčani redno romali.

Gradnja kranjske župnijske cerkve je pomembno vplivala na razvoj poznogotske arhitekture ne le na Gorenjskem, temveč tudi na Dolenjskem, Goriškem in Notranjskem. Predvsem so pod njenim vplivom nastale župnijske cerkve v Škofji Loki, Radovljici in Cerknici, t.i. Mojster kranjskega ladijskega oboka in njegova šola pa sta pustila sledi še v številnih drugih cerkvah po Sloveniji.

S postavitvijo gotskega oltarja na začetku 16. stol. je bila gradnja gotske cerkve v Kranju zaključena. Kmalu pa so sledila popravila in dopolnila, zlasti cerkvene opreme. Leta 1631 je bilo v cerkvi 12 oltarjev. Cerkev je leta 1791 dobila nov, baročni glavni oltar. Podobo zanj je izdelal kranjski slikar Leopold Layer, menzo tega oltarja pa je kranjski dekan Jožef Golmajer pridobil iz ukinjenega ljubljanskega frančiškanskega samostana, za katerega jo je 1748. leta izdelal sodelavec znamenitega Francesca Robbe - Carlo Bombassi. Menza še danes krasi kranjsko cerkev. Zaradi požara je pred letom 1772 zvonik dobil novo, čebulasto streho, pred koncem stoletja pa je bila na mestu stopniščnega stolpiča zgrajena nova zakristija. Med leti 1831 in 1836 je bil v novogotskih formah povišan zvonik in zgrajena nova piramidalna streha. Iz naslednje faze regotizacije cerkve so se ohranili posamezni deli opreme – klopi, orgelska omara in ograja pevske empore (1855). Večje sledi pa so zapustila obnovitvena dela iz časa župnika Antona Mežnarca (1874 – 1900): nadzidava severne kapele in zakristije ob prezbiteriju (1877), dve novi okni v prezbiteriju in tri nova visoka okna v južni steni ladje (dotlej so bila v tej steni le okna, kakršno je ohranjeno pod pevskim korom), dve okni iz prvega nadstropja zakristije v prezbiterij, novo cerkveno ostrešje, rekonstruiran šilast obok med ladjo in prezbiterijem, slavolok med prezbiterijem in severno kapelo. Leta 1890 sta bila naročena dva stranska kamnita oltarja (kamnosek Feliks Toman, kipe je izdelal južnotirolski kipar Christijan Mahlknecht), dva stranska gotska portala sta bila prestavljena v zahodno steno, v prezbiteriju okrog oltarja je bil položen nov tlak, 1893 so bile kupljene vse postaje križevega pota in spovednice. Celotna cerkev je bila 1891 in 1892 na novo poslikana (slikar Matija Bradaška), izdelane so bile tudi nove orgle (delavnica bratov Zupan iz Kamne Gorice). Za kritje stroškov te obnove je župnik Mežnarec leta 1886 prodal stari gotski oltar na Dunaj. Naslednja obnova se je pričela leta 1934, vodil jo je deželni konservator France Stele. Zaradi dotrajanosti je bil zamenjan glavni oltar, novega (sedanjega) je izdelal arhitekt Ivan Vurnik (slike Helena Vurnik, kipi France Gorše), prebeljena je bila Bradaškova poslikava, s čimer je prišla ponovno do izraza gotska arhitektura, odkrite in restavrirane so bile gotske freske na stropu ladje (slikar Matej Sternen), odstranjen je bil omet s kamnitih stebrov v ladji, na novo so bile postavljene spovednice v zidne niše, leta 1938 je bil postavljen še Marijin oltar na južni steni slavoloka (arhitekt Ivan Vurnik). Leta 1943 so bile zamenjane orgle (Franc Jenko iz Šentvida, vgrajene v staro orgelsko omaro), v letih 1962 in 1963 pa je bila urejena krstna kapela vključno z novimi vitraji v oknih (slikar Stane Kregar), 1966 do 1969 zamenjani vsi vitraji v cerkvi (slikar Stane Kregar, delavnica Staklo Zagreb, mojster Pavle Sušilović). Vitraji so ikonografsko usklajeni z oltarji in prostorom. V prezbiteriju skrajno levo okno predstavlja Stvarjenje in Staro zavezo, sledi Nova zaveza s simboli evangelistov in papeža, v srednjem oknu je predstavljeno Poveličanje sv. Križa, desno od njega so simboli evharistije, skrajno desno pa je predstavljeno Cerkveno leto (z značilnostmi praznikov). Okna v severni steni predstavljajo Devištvo in simboliko litanij Matere Božje, na desni pa simbole evharistije in Srca Jezusovega. Južna stena ima v levem oknu predstavljene Marijine čednosti, v sredini simbole mučeništev sv. Neže in sv. Uršule, na desni pa simbole oblasti odpuščanja grehov.

Zadnji obsežnejši posegi v kranjski župnijski cerkvi, ki so bili izvedeni za časa župnika Stanislava Zidarja, so se omejevali na reševanje zahtevnih statičnih problemov. Tako rekoč v zadnjem hipu je bilo v letih 1998 do 2000 ustavljeno nevarno razpiranje cerkvenih sten. Istočasno je bilo obnovljeno ostrešje in zamenjana kritina na cerkvi in zvoniku. V letih 2004 do 2010 pa so bila izvedena še obsežna restavratorska dela v cerkveni ladji in njeni opremi.