W czasie wykopalisk pod kościołem znaleziono drewniane resztki jednej lub kilku budowli, a kościoły były zwykle budowane na miejscu wcześniejszych świątyń pogańskich.
W tym czasie dokonywała się ostateczne chrystianizacja Szwecji. Z drugiej strony był to też okres walk o władzę. To właśnie w okolicach Gamla Uppsala został ok. 1160 zamordowany król Eryk IX, uznany później za świętego. Z tego względu Gamla Uppsala stała się siedzibą biskupią, która została przeniesiona tu z Sigtuny. W 1164 Gamla Uppsala została podniesiona do godności siedziby arcybiskupiej; przedtem Szwecja podlegała duńskiej archidiecezji w Lund. Kult św. Eryka, który wówczas zaczął się kształtować, został szybko powiązany z nową archidiecezją, a sam święty stał się wkrótce patronem królestwa Szwecji.
Po pożarze w roku 1240 część katedry została rozebrana, ale dobudowano zakrystię i przedsionek. W XV wieku dodano podziemia oraz malowidła ścienne.
Ok. 1273 siedziba arcybiskupa została oficjalnie przeniesiona do dzisiejszej Uppsali, gdzie tuż przedtem rozpoczęto wznoszenie katedry. Na nowe miejsce, które wcześniej nazywało się Östra Aros, przeniesiono również nazwę Uppsala. Natomiast dotychczasowa katedra w Gamla Uppsala została zdegradowana do rangi zwykłego kościoła parafialnego. W XV w.