Die Kirche San Vicente wurde zu Ehren der Hl. Martyrer Vicente, Sabina und Cristeta errichtet, die im 4. Jahrhundert nach Christus unter der Herrschaft des Kaisers Diokletian und unter der Verwaltung des Gouverneurs Dacianus den Martyrertod erlitten.Nach der Vollstreckung der Todesstrafe wurden die Leichname der drei Geschwister einen steilen Felsabhang in der Nähe hinabgeworfen.In der Nähe des Hinrichtigungsortes wurde die erste Kirche errichtet. Nach der Überlieferung war diese das Werk eines Juden, der sich während der Hinrichtung bekehrt hatte und der später selbst dort begraben sein soll.Während der Zeit der muslimischen Invasion wurde das Andenken an die Heiligen aufrecht erhalten, aber die Kirche verfiel nach und nach, bis sie schliesslich ganz verfallen war. Von ihrem Grundriss ist nichts mehr enthalten.

Mit der Wiederbesiedelung der Stadt, die am Ende des 11. Jahrhunderts von dem Grafen Raimundo von Burgund und auf Veranlassung des Königs Sancho VI und seiner Frau Doña Urraca durchgeführt wurde, wurde der Bau der neuen Basilika gleichzeitig mit dem Stadtmauerbau und dem Bau der Kathedrale begonnen.

Während des ersten Drittels des 12. Jahrhunderts beginnt man nach dem Vorbild von San Isidoro in Leon und Santiago de Compostela mit dem Bau der Krypta und der Apsiden der Kirche. Die Arbeiten gehen langsam, aber stetig voran und beinhalten Stile von der Hochromanik bis zur Spätgotik.

Chronologie der Baustile

Frühchristlicher Baustil (4.-5. Jhdt.): Reste von spatrömischen Grabmählern in der Krypta.

Romanik (1.Drittel des 12. Jhdts.): Krypta, Hauptgebäude, 4 Abschnitte in den Kirchenschiffen, Gitter und zwei Skulpturen an der Südpforte.

Frühgotik (letztes Drittel des 12 Jhdts.): Nartex, Emporen und Türme; Gewölbe des Mittelschiffes, Westportal und Skulpturen mit der Darstellung der Verkündigung und des Königs an der Südseite sowie das Grabmahl der Hl. Martyrer

Gotik (14.Jhdt.): Zimborium und Südpforte

Isabelinische Gotik (15. Jhdt.): Abschluss des Nordturms, Sakristei (vermutlich um 1477) und der Baldachin des Grabmahls

Spätrenaissance (17.Jhdt.): um 1609 entwirft Juan Gutiérrez de Mora das Grabmahl für San Pedro del Barco

Churriguresker Barock (18. Jhdt): Hochaltar

Restaurierung (19. Jhdt.): durchgeführt von E. M. Repullés y Vargas. Am 26. Juli 1882 wird die Kirche zum Nationaldenkmal ernannt.