מיתוס הקשור למקור קדושת האתר גורס כי השליח יעקב בן זבדי הביא את בשורת הנצרות לקלטים בחצי האי האיברי. ב-44 לספירה, ראשו נערף בירושלים. שרידיו הובאו בחזרה לגליסיה, ובעקבות רדיפות הספרדים הנוצרים בידי הרומאים, ננטש קברו במאה ה-3. קברו נתגלה מחדש ב-814 בידי פלאיו (Pelayo), נזיר נוצרי, שראה אורות מוזרים בשמי הלילה. הבישוף תאודמיר מאיבריה הכיר בכך כנס והודיע על כך למלך ממלכת אסטוריאס אלפונסו השני (791–842) אשר הורה על בניית קפלה באתר. על פי האמונה היה המלך לצליין הראשון שעלה לרגל אל הכנסייה. בעקבות זאת, הוקמה כנסייה ראשונה באתר ב-829. כנסייה שנייה בסגנון פרה-רומנסקי, הוקמה במקום ב-889 בהוראת המלך אלפונסו השלישי, מלך לאון, דבר שהוביל לפיתוח האתר כאתר צליינות מקובל וחשוב. המיתוס נוצל בידי מלכי ספרד הנוצרית כדי לבססה כממלכה נוצרית ולגרש את המורים מחצי האי האיברי. ב-997 נשרפה הכנסייה בידי מוחמד איבן-אבי אמיר (938–1002), מפקד צבא החליפות קורדובה. הדלתות והפעמונים, נישאו בידי השבויים הנוצריים לקורדובה, ושם הותקנו במסגד אלג'אמה. כאשר קורדובה נכבשה בידי המלך פרדיננד השלישי, מלך קסטיליה ב-1236, אותם דלתות ופעמונים נישאו בידי שבויים מוסלמים לטולדו, שם הותקנו בקתדרלת טולדו.

בניית הקתדרלה הנוכחית, בסגנון רומנסקי, החלה ב-1075 תחת שלטונו של אלפונסו השישי, מלך קסטיליה (1040–1109) ובחסותו של הבישוף דייגו פלאס (Peláez). היא בנויה בעיקר מגרניט. הבנייה הופסקה מספר פעמים, והאבן האחרונה הונחה ב-1122[1], אך גם אז בניית הקתדרלה טרם הסתיימה. הקתדרלה נחנכה ב-1128 בנוכחות המלך אלפונוסו התשיעי, מלך לאון. בשל חשיבותה כאתר צליינות, הייתה הכנסייה למקום מושבו של בישוף ב-1075, וכעבור זמן לא רב, בשנת 1100, היא הועלתה לדרגת מושבו של ארכיבישוף בידי האפיפיור אורבנוס השני. אוניברסיטה קתדרלית נוספה ב-1495. הקתדרלה שופצה והורחבה בין המאה ה-16 למאה ה-18 בסגנון אדריכלות הבארוק.

לפי ה-Codex Calixtinus (אנ'), הארכיטקטים האמונים על הבניה היו "ברנרד הזקן", העוזר שלו "רוברטוס גלפרינוס", וייתכן שלאחר מכן גם "אסטבן, המסטר של עבודות הקתדרה". בשלב האחרון, "ברנרד הצעיר (הבן)" סיים את בניית הקתדרלה, כאשר גלפרינוס היה אחראי על התיאום. הוא גם בנה מזרקה מונומנטלית בקדמת השער הצפוני ב-1122.