Według legendy apostoł Jakub Większy prowadził działalność misyjną wśród Celtów zamieszkujących Półwysep Iberyjski. W 44 zginął śmiercią męczeńską w Jerozolimie. Jego ciało zostało wkrótce przeniesione do Galicji. W dobie prześladowań chrześcijan zamieszkujących ten teren, w III w. grób wraz ze szczątkami św. Jakuba został porzucony. W 813 szczątki apostoła zostały odnalezione dzięki, jak głosi tradycja, Eremicie Pelayo, który podczas swoich poszukiwań w nocy widział deszcz gwiazd spadających na pobliskie wzgórze. Podzielił się swoją wizją z miejscowym biskupem Teodomirem z Iria, który zleciwszy zbadanie sprawy, odkrył kamienny grobowiec zawierający szczątki męczennika. Wybudowano w tym miejscu kościół, a nazwa Compostela (pochodzi z łacińskiego campus stellae – co oznacza pole gwiazd) przypomina cudowne wydarzenie związane z tym miejscem. Biskup Theodemir uznał to wydarzenie za cud i powiadomił króla Asturii Alfonsa II. Król zlecił wznieść kaplicę na miejscu cudownego odnalezienia. Następnie świątynię powiększano, w 829 i w 899 w stylu wczesnoromańskim. Patronat nad ostatnią rozbudową objął król Leónu Alfons III Wielki. W 997 r. podczas ekspansji Arabów na półwyspie Iberyjskim Mohammed ibn-Abi Amir (938-1002), dowódca wojsk Kalifatu Kordowy, kazał zniszczyć kościół. Ozdobne wrota i dzwony przeniesiono do Wielkiego Meczetu w Kordowie. Kiedy Kordowę zdobyły w 1236 wojska króla Ferdynanda III Kastylijskiego, te same zdobycze przeniesiono do katedry w Toledo.

Budowa obecnej monumentalnej świątyni rozpoczęła się w 1075 za panowania Alfonsa VI Kastylijskiego i rządów biskupa Diego Peláeza. W swoim planie nawiązuje do wzniesionego z cegły kościoła klasztornego św. Sernina w Tuluzie, z tym, że świątynię w Santiago zbudowano przede wszystkim z granitu. Budowla powstawała w kilku fazach i jak mówi Księga św. Jakuba (Liber Sancti Iacobi), ostatni kamień został położony w 1122. Uroczysta konsekracja katedry miała miejsce w 1211. Wśród świadków poświęcenia był m.in. król Leónu Alfons IX.

Ze względu na znaczenie tego miejsca pielgrzymkowego już podczas budowy zmieniał się status świątyni. Status kościoła katedralnego kościół otrzymał w 1075, natomiast w 1100 papież Urban II polecił założyć przy katedrze siedzibę arcybiskupa. W 1495 przy archikatedrze powstał uniwersytet.

Kościół był wielokrotnie przebudowywany w XVI–XVIII w.