Sverige blev en egen kyrkoprovins med ärkebiskop för 850 år sedan. Den första domkyrkan i Uppsala finns fortfarande kvar och kallas numera Gamla Uppsala kyrka.
Omkring 1270 började en ny domkyrka i Östra Aros, längre söderut längs Fyrisån, att byggas. Namnet Uppsala flyttade med till den nya domkyrkan och namnet Östra Aros försvann. Erik den heliges reliker, kyrkans stora klenod, flyttades också från den förra domkyrkan i Gamla Uppsala redan 1273.
Redan tidigt skrevs kontrakt med byggmästaren och arkitekten Estienne de Bonnueill från Frankrike. Hans medarbetare har troligen utfört stora delar av kapellen i domkyrkans östra del, högkoret samt södra och norra portalerna.
År 1331 bad kung Magnus Eriksson upplänningarna att än en gång skänka pengar till byggkassan så att domkyrkan ”genom Guds nåd på kort tid" kunde färdigställas. Kungens vädjan och spår i väggarna visar att det övervägdes att låta domkyrkan bestå av enbart högkoret och kapellen runtomkring samt av ett tvärskepp.
Men senare under 1300-talet fullföljdes trots allt den ursprungliga planen med ett långhus i väster. Byggmästaren Nikolaus från Västerås var en av dem som ansvarade för långhusbygget. Det fick ett enklare utförande än domkyrkans östra del.