Pierwszym kościołem, który powstał na miejscu obecnej katedry była, według Adama z Bremy, drewniana świątynia zbudowana przez króla Haralda Sinozębego, w murach której został później pochowany. Po tej budowli nie odnaleziono żadnych śladów. W XI w. drewniany kościół Trójcy Świętej, jak pierwotnie zwano późniejszą katedrę w Roskilde, został zastąpiony przez świątynię murowaną. Inicjatorką budowy była ks. Estrida, siostra króla Kanuta Wielkiego. Nowy kościół poświęcił ok. 1080 r. biskup Svend Normand, który ukończył budowę świątyni. Świątynia była bazyliką trójnawową z wieżami od strony zachodniej. Od strony północnej do świątyni przylegał budynek klasztoru służący za mieszkanie dla księży pełniących posługę w kościele. Około 1100 r. biskup Arnold otoczył całość murem i fosą, których resztki zalegają pod obecnym placem koło katedry. Plac ten do ok. 1820 r. służył jako cmentarz przykatedralny.

W poł. XII w. biskup Zelandii Absalon zainicjował przebudowę kościoła Trójcy Świętej w Roskilde w nowym stylu, który przywędrował do Danii, w gotyku. Rozpoczęte przez niego dzieło kontynuował biskup Skanii Anders Sunesøn i jego brat biskup Roskilde Peder Sunesøn, który podobnie jak Absalon, zdobył wykształcenie w Paryżu. Miało to decydujący wpływ na ostateczny kształt świątyni, która została przebudowana w stylu francuskiego gotyku, co było wtedy czymś zupełnie wyjątkowym w Danii. Budowa, do której zużyto ok. 3 milionów cegieł, została ukończona w ok. 1280 r. W XIV w. do katedry dodano dwie zachodnie wieże, ale charakterystyczne iglice wieńczące katedralne wieże zostały dodane dopiero w czasach panowania Chrystiana IV (1635).

14 maja 1443 roku, w wyniku pożaru, który wybuchł i ogarnął znaczną część Roskilde, zniszczeniu uległo pokrycie dachowe katedry. Pod wpływem wysokich temperatur popękały również szyby. Fundusze na odbudowę uszkodzonej katedry zebrano dzięki podpisaniu przez biskupów Danii zgody na przyznanie 40 dni odpustu darczyńcom na ten cel[1].