Krščanstvo se je najprej razširilo v mestih, kjer je ustanovilo svoje prve skupnosti, že leta 425 n. št. (spomnimo, leta 313 je cesar Konstantin I. Veliki označil konec verskega preganjanja v rimskem cesarstvu) pa je bil sprejet zakon o ustanovitvi škofij v mestih. Ker je bil Krk po prihodu krščanstva že pomembno mesto, je tako kot druga sredozemska središča dobil škofijo že v najzgodnejših časih krščanstva. Kjer pa je bila ustanovljena škofija, je bilo dovoljeno graditi tudi cerkve. Zato je bila krška stolnica, posvečena Blaženi Devici Mariji, kot najpomembnejši arhitekturni in umetniški spomenik na otoku Krk zgrajena že v 5. stoletju na ostankih rimskih term, in sicer kot triladijska zgodnjekrščanska bazilika, tradicionalno orientirana v smeri vzhod–zahod. Triladijska romanska stavba, katere osrednja ladja se zaključi z mnogokotno apsido, stranski ladji pa z ravnima, se je ohranila do danes.

Prva znana omemba stolnice je v darovnici škofa Ivana iz leta 1186, v kateri piše benediktincem o njihovi obveznosti do nje. V svoji dolgi in bogati zgodovini je bila stolnica večkrat dograjena, posebno pozornost pa vzbuja frankopanska, arhitekturno edinstvena poznogotska kapela, prizidana ob severni zid. Nad mnogokotnim tlorisom je v njeni notranjosti zvezdasti obok, okrašen s ščiti z grbi krških knezov, glede na uporabo njihovega novega grba pa je morala biti sama kapela zgrajena po letu 1430 in se interpretira kot knežja naložba.

O prvotni baziliki danes pričajo elementi, kot so sodčasti krstni kamen (piscina), ostanki talnega mozaika in razni okraski v kamnu. 

Osrednji del parterja stolnice hrani grob Ludovica Cicute (Ljudevita Čikute), suprakomita krške galeje Cristo Ressussitato, ki je na strani Svete lige sodelovala v enem najbolj znanih pomorskih spopadov v evropski zgodovini – bitki pri Lepantu leta 1571. 

Del bogatega inventarja stolnice so dragocene poslikave baročnih mojstrov Cristofora Tasce (oltarni prostor) in Nicole Grassija (svetišče Srca Jezusovega), masivne lesene ročno izdelane izdelke – prižnico, škofovski prestol, omaro, ki prekriva celotno steno zakristije, in tamkajšnji oltar – pa podpisujejo mojstri Ivan Sneit ter Mihovil in Franjo Zierer. Veličastne orgle na koru so delo beneškega izdelovalca orgel Gaetana Callidea iz leta 1815.

Zgodnjekrščanske cerkve na začetku niso imele zvonikov, tako ga tudi krška stolnica ni imela. Obstoječi zvonik je bil zgrajen šele leta 1515 v gotskem slogu, zaradi pomanjkanja prostora pa so ga postavili ob stranski del cerkve sv. Kvirina. Potem ko je šilasti vrh stolpa uničil udar strele, se je leta 1765 po projektu beneškega arhitekta Pietra Checchija začela gradnja prepoznavne baročne kupole, na vrhu katere so leta 1767 postavili angela s trobento, izdelanega v Benetkah.