It is widely believed that the Apostle James the Greater was responsible for introducing Christianity to the Iberian Peninsula. His body was taken from Jerusalem to Galicia in a stone boat after his execution in the year 44. His tomb was left unattended in the third century after Roman persecutions of Christians in Hispania. The hermit Pelayo (Pelagius) supposedly stumbled onto this tomb in 814 after being captivated by unexplainable starlight. King Alfonso II of Asturias was notified of the miracle by Bishop Teodomiro of Iria, who then had a chapel built there. According to myth, the monarch was the first devotee to visit this holy site. An early church was constructed there in 829, and by 899, at the behest of King Alfonso III,8, the site had become a major pilgrimage destination. In 997, the Caliph of Cordoba's army was led by Almanzor, who ordered the destruction of this early church. The aljama mosque in Córdoba now features the church's doors and bells, which were brought there by Christian captives. Doors and bells similar to those in the Cathedral of Santa Mara de Toledo were brought to Toledo by Muslim prisoners after Córdoba was conquered by King Ferdinand III of Castile in 1236.

The current cathedral was begun in 1075 under King Alfonso VI and Bishop Diego Peláez, and it was modeled after the largest Romanesque structure in France, the monastery brick church of Saint Sernin in Toulouse. The stone used in construction of the church was of the highest quality. The Liber Sancti Iacobi states that the final stone was put in 1122 and the cathedral was consecrated in 1128, despite the fact that construction halted multiple times. The architects were "Bernard the Elder, a marvellous master," his assistant Galperinus Robertus, and probably "Stephen, master of cathedrals," as stated in the Codex Calixtinus. Last but not least, "Bernard the Younger" (perhaps Stephen's son) finished up the construction while Galperinus oversaw coordination. In 1122, he also constructed a massive fountain in the square in front of the northern doorway.

The chapter commissioned the master Mateo to build the crypt and the Portico of Glory in 1168, and the cathedral was consecrated on Thursday morning of the second week of Easter in 1211,N 2 by Archbishop Pedro Muiz in the presence of King Alfonso IX and his son, as well as numerous ecclesiastical and civil authorities.

In 1075, the church was recognized as an episcopal see, and by 1120, because to the efforts of Bishop Diego Gelmrez and the increasing popularity of the site as a pilgrimage destination, it was elevated to the rank of archbishopric. Between the 16th and 18th centuries, the cathedral was expanded and refurbished.