Es wird allgemein angenommen, dass der Apostel Jakobus der Große für die Einführung des Christentums auf der Iberischen Halbinsel verantwortlich war. Sein Leichnam wurde nach seiner Hinrichtung im Jahr 44 in einem Steinboot von Jerusalem nach Galicien gebracht. Sein Grab wurde im dritten Jahrhundert nach den römischen Christenverfolgungen in Hispanien unbeaufsichtigt gelassen. Der Einsiedler Pelayo (Pelagius) stolperte angeblich 814 über dieses Grab, nachdem er von unerklärlichem Sternenlicht fasziniert war. König Alfons II. von Asturien erfuhr von diesem Wunder durch Bischof Teodomiro von Iria, der daraufhin dort eine Kapelle errichten ließ. Der Mythos besagt, dass der Monarch der erste Gläubige war, der diese heilige Stätte besuchte. Im Jahr 829 wurde dort eine erste Kirche errichtet, und im Jahr 899 wurde der Ort auf Geheiß von König Alfons III.8 zu einem bedeutenden Wallfahrtsort. Im Jahr 997 befahl der Kalif von Córdoba unter der Führung von Almanzor die Zerstörung dieser ersten Kirche. In der Aljama-Moschee in Córdoba befinden sich heute die Türen und Glocken der Kirche, die von christlichen Gefangenen dorthin gebracht wurden. Türen und Glocken, die denen der Kathedrale Santa Mara de Toledo ähneln, wurden von muslimischen Gefangenen nach der Eroberung Córdobas durch König Ferdinand III. von Kastilien im Jahr 1236 nach Toledo gebracht.

Die heutige Kathedrale wurde 1075 unter König Alfons VI. und Bischof Diego Peláez nach dem Vorbild des größten romanischen Bauwerks in Frankreich, der Klosterkirche Saint-Sernin in Toulouse, errichtet. Der für den Bau der Kirche verwendete Stein war von höchster Qualität. Im Liber Sancti Iacobi heißt es, dass der letzte Stein 1122 gesetzt und die Kathedrale 1128 geweiht wurde, obwohl der Bau mehrmals unterbrochen wurde. Die Architekten waren "Bernhard der Ältere, ein wunderbarer Meister", sein Assistent Galperinus Robertus und wahrscheinlich "Stephan, der Meister der Kathedralen", wie es im Codex Calixtinus heißt. Nicht zuletzt beendete Bernhard der Jüngere" (vielleicht Stephans Sohn) den Bau, während Galperinus die Koordinierung übernahm. Im Jahr 1122 errichtete er auch einen großen Brunnen auf dem Platz vor dem Nordportal.

Das Kapitel beauftragte 1168 den Meister Mateo mit dem Bau der Krypta und des Portikus der Herrlichkeit, und die Kathedrale wurde am Donnerstagmorgen der zweiten Osterwoche 1211,N 2 von Erzbischof Pedro Muiz in Anwesenheit von König Alfons IX. und seinem Sohn sowie zahlreicher kirchlicher und ziviler Behörden geweiht.

Im Jahr 1075 wurde die Kirche als Bischofssitz anerkannt, und im Jahr 1120 wurde sie dank der Bemühungen von Bischof Diego Gelmrez und der zunehmenden Beliebtheit des Ortes als Pilgerziel in den Rang eines Erzbistums erhoben. Zwischen dem 16. und 18. Jahrhundert wurde die Kathedrale erweitert und renoviert.