Andre Maria Zuriaren elizatik gertu eraiki zuten kolegiata. Tuterako meskita nagusiaren ondoan zegoen eliza hura mozarabiarra[[mozarabiar]]ra zen, eta huraxe izan zen kristauek Tutera konkistatu ondoren beste elizen gainean eskumena izan zuen lehenengo eliza.
Katedrala XII. mendearen bukaeratik XIII. mendearen hasiera bitartean eraiki zuten, IX. mendeko meskitaren orubearen gainean, hispaniar-langedoctar eskolako arkitektura zistertarraren ereduari jarraiki. Aipatutako meskita hori [[Musa ibn Musa|Musa II.ak]], Tuterako jaunak eta [[Banu-KasitarrenQasi]]tarren buruzagiak, eraikiarazi zuen, eta X. mendean eraberritu egin zuten Tuybitarren[[Banu Tujibi|Tujibitarren]] gidaritzapean, eta meskita haren elementu batzuk baliatu zituzten katedral berria eraikitzeko. Katedrala eraikitzeko lanak 1168 inguruan hasi ziren, [[Antso Jakituna]] errege zela, urte hartan FortonFortun priorrakprioreak meskita zaharraren ondoan zeuden etxe batzuk erosi baitzituen eraikuntza berrirako baliatzeko.
1188an lanak nahiko aurreratuta zeuden, eta eliza erabilgarria zen jadanik. Eraikuntzaren lehenengo garaiari dagozkio burualdea eta gurutzadura. Gero, inguruko hormak eta fatxada nagusiko [[Azken JudiziokoJudizio]]ko ataria eraiki zituzten.
Tarragonako RamónErramun de RocalertiRocabertí apezpikuak 1204an sagaratu zuen aldare-harria. Garai hartako dokumentuen arabera, XIII. mendeko bigarren erdian eraikitze-lanek aurrera jarraitzen zuten; Domingo Perez zen lanen maisua 1262an eta 1263an. Katedralaren eraikuntzan harginen marka batzuk gorde dira.
