On pense généralement que c'est l'apôtre Jacques le Majeur qui a introduit le christianisme dans la péninsule ibérique. Son corps a été transporté de Jérusalem à la Galice dans un bateau de pierre après son exécution en 44. Sa tombe a été laissée sans surveillance au troisième siècle, après les persécutions romaines contre les chrétiens en Hispanie. L'ermite Pelayo (Pélage) serait tombé sur cette tombe en 814 après avoir été captivé par une lumière d'étoile inexplicable. Le roi Alphonse II des Asturies fut informé du miracle par l'évêque Teodomiro d'Iria, qui fit alors construire une chapelle. Selon la légende, le monarque fut le premier fidèle à visiter ce lieu saint. Une première église y fut construite en 829 et, en 899, sur l'ordre du roi Alphonse III8, le site devint un important lieu de pèlerinage. En 997, l'armée du calife de Cordoue, dirigée par Almanzor, a ordonné la destruction de cette église primitive. La mosquée aljama de Cordoue présente aujourd'hui les portes et les cloches de l'église, apportées par des captifs chrétiens. Des portes et des cloches similaires à celles de la cathédrale Santa Mara de Tolède ont été apportées à Tolède par des prisonniers musulmans après la conquête de Cordoue par le roi Ferdinand III de Castille en 1236.

La cathédrale actuelle a été commencée en 1075 sous le roi Alphonse VI et l'évêque Diego Peláez, et a été modelée sur la plus grande structure romane en France, l'église en briques du monastère de Saint-Sernin à Toulouse. La pierre utilisée pour la construction de l'église était de la plus haute qualité. Le Liber Sancti Iacobi indique que la dernière pierre a été posée en 1122 et que la cathédrale a été consacrée en 1128, bien que la construction ait été interrompue à plusieurs reprises. Les architectes étaient "Bernard l'Ancien, un maître merveilleux", son assistant Galperinus Robertus, et probablement "Étienne, maître des cathédrales", comme l'indique le Codex Calixtinus. Enfin, "Bernard le Jeune" (peut-être le fils d'Étienne) a achevé la construction tandis que Galperinus en assurait la coordination. En 1122, il construisit également une fontaine massive sur la place devant la porte nord.

En 1168, le chapitre confie au maître Mateo la construction de la crypte et du portique de la Gloire, et la cathédrale est consacrée le jeudi matin de la deuxième semaine de Pâques en 1211,N 2 par l'archevêque Pedro Muiz, en présence du roi Alphonse IX et de son fils, ainsi que de nombreuses autorités ecclésiastiques et civiles.

En 1075, l'église est reconnue comme siège épiscopal et en 1120, grâce aux efforts de l'évêque Diego Gelmrez et à la popularité croissante du site en tant que destination de pèlerinage, elle est élevée au rang d'archevêché. Entre le XVIe et le XVIIIe siècle, la cathédrale a été agrandie et rénovée.