Kort tid etter Olavs helligkåring i 1031 ble det reist et lite kapell i tre på stedet hvor han lå gravlagt det første året. Rundt år 1070 lot Olav Kyrre kapellet erstatte av ei steinkirke. Kristkirka var den største kirka i Norge, og starten på det som skulle bli Nidarosdomen. Sølvskrinet med Olav den helliges kropp sto ved alteret i kirka.
Etter hvert som historien om Olav den helliges mirakler spredte seg, tok stadig flere pilegrimer veien til Nidaros. I 1152-53 kom Pavens utsending, kardinal Nicolaus Breakspeare til Nidaros for å opprette et nytt erkebispesete for Norge og øyene i havet i vest. Nidaros erkebispedømme omfattet et stort område, og inntekter fra Nidarosprovinsen bidro til å finansiere en storstilt utbygging av Kristkirka.
Fra midten av 1100-tallet ble det reist tverrskip mot nord og syd. Disse utgjør den eldste delen av kirka som fremdeles står i dag. Tverrskipet er bygd i romansk stil, slik også Kristkirka var, med tykke, massive murer, små vindusåpninger og runde buer. Mot slutten av 1100-tallet begynte den gotiske stilen å gjøre seg gjeldende også i Norge. Kapittelhuset fra 1160-tallet er bygd i en overgangsstil, med elementer av både romansk og gotisk arkitektur.
Oktogonen - det åttekantede høykoret i unggotikk, er den første delen som ble reist i gotisk stil. Olavsskrinet sto på en sokkel inne i midtrommet, og pilegrimene kom nær relikvien når de gikk i koromgangen rundt oktogonen. Rundt år 1200 ble Kristkirken revet, og erstattet av det nye koret i Nidarosdomen. Fra midten av århundret reiste det store skipet i høygotikk seg i vest, og katedralen sto ferdig rundt år 1300. De gotiske delene av Nidarosdomen karakteriseres av høye steinhvelv, store vindusflater og spisse buer. På utsiden av kirka ser man strebebuer og -pilarer som støtter opp veggene.
Håndverkerne som bygde katedralen var organisert i en bygghytte, der mange ulike fag var representert. Spor etter dem som bygde katedralen finnes fremdeles i form av steinhuggermerker i murene i kirka.