Po legendi je apostol sveti Jakob prinesel krščanstvo na Iberski polotok.[1][2] Po legendi je puščavnik Pelagij znova odkril to grobnico leta 814 po tem, ko je bil priča čudnim lučem na nočnem nebu. Irski škof Teodomir je to priznal kot čudež in o tem obvestil kralja Asturije in Galicije, Alfonza II. (791–842). Kralj je na tem mestu naročil gradnjo kapelice. Legenda pravi, da je bil kralj prvi romar v to svetišče. Sledila je prva cerkev leta 829, nato pa leta 899 n. št. predromanska cerkev, ki jo je naročil kralj Alfonz III. Leonski[3], kar je povzročilo postopen razvoj tega glavnega romarskega kraja.[4]

Leta 997 je zgodnjo cerkev pretvoril v pepel Ibn Abi Aamir (znan kot Almanzor) (938–1002), poveljnik vojske kalifata v Córdobi. Poveljnika Al Andaluza so ob napadu spremljali njegovi vazalni krščanski gospodje, ki so prejeli del plena. Grob in relikvije sv. Jakoba so pustili nedotaknjene. Vrata in zvonovi, ki so jih lokalni krščanski ujetniki nosili v Córdobo, so bili dodani Aljamski mošeji.[5] Ko je leta 1236 kralj Ferdinand III. Kastiljski prevzel Córdobo, so ta vrata in zvonove muslimanski ujetniki prepeljali v Toledo, da bi jih vstavili v Toledsko stolnico.

Gradnja sedanje stolnice se je začela leta 1075 pod vladavino Alfonza VI. Kastiljskega (1040–1109) in pod pokroviteljstvom škofa Diega Peláeza. Zgrajena je bila po istem načrtu kot samostanska opečnata bazilika sv. Saturnina v Toulousu, verjetno največja romanska stavba v Franciji. Zgrajena je bila predvsem iz granita. Gradnja je bila večkrat ustavljena in po besedah Liber Sancti Iacobi je bil zadnji kamen položen leta 1122. Toda do takrat gradnja stolnice zagotovo ni bila končana. Stolnica je bila posvečena leta 1211 v prisotnosti kralja Alfonza IX. Leonskega.[6][7]

Po Codex Calixtinusu so bili arhitekti "Bernard starejši, čudovit mojster", njegov pomočnik Robertus Galperinus in kasneje morda "Esteban, mojster stolnih del". V zadnji fazi je "Bernard, mlajši" dokončal stavbo, Galperinus pa je bil zadolžen za koordinacijo. Leta 1122 je pred severnim portalom zgradil tudi monumentalni vodnjak.

Mesto je leta 1075 postalo škofovsko središče, cerkev pa njegova stolnica. Zaradi vse večjega pomena kot romarskega kraja jo je papež Urban II. leta 1100 povzdignil na nadškofovsko sedež. Leta 1495 je bila dodana univerza.

Stolnico so v 16., 17. in 18. stoletju razširili in olepšali z dodatki.