Mandó construir este templo doña Mayor de Castilla, viuda de Sancho III de Navarra hacia el año 1066. Fue la iglesia del monasterio de San Martín de Tours, dónde doña Mayor se retiró después de la muerte de su esposo.

Entre 1894 y 1904 fue desmontada y reconstruida por Manuel Aníbal, eliminando todos los elementos añadidos a lo largo de los siglos e "inventándose" aquellos que habían desaparecido, como parte de la torre sur, la puerta del transepto o bien casi noventa ménsulas.  Es por este motivo que da la sensación de ser "muy nueva".

Durante esta restauración, algunos de los capiteles fueron sustituidos por réplicas y actualmente se conservan en el Museo Arqueológico de Palencia.

Pese a ser uno de los templos más representativos del románico español, destaca por su sobriedad de formas. Tiene planta basilical de tres naves acabadas en tres ábsides semicirculares.

Los ábsides destacan por sus grandes ventanas. En el ábside principal encontramos tres, mientras que en los laterales sólo se abren dos.

Todas las ventanas están decoradas con una arquivolta de baquetón, que se apoya en dos columnas. Rodea el conjunto un guardapolvo ajedrezado.

Sus capiteles están decorados con motivos vegetales, entrelazados, aves enfrentadas, bestias y algunas figuras humanas, algunas de ellas de tipo erótico.

El ábside principal está dividido en tres espacios mediante dos columnas adosadas, que decrecen en diámetro a medida  que aumentan en altura. Están rematadas con capiteles vegetales. También está dividido mediante dos líneas de imposta ajedrezadas. Una de ellas recorre el tambor absidal justo por debajo de las ventanas, mientras que la otra lo hace en el punto de arranque del arco de las mismas.

La decoración de la cabecera se completa con una cornisa ajedrezada, que se apoya en canecillos esculpidos.

Las naves están cubiertas con bóvedas de cañón, reforzadas por arcos fajones.

Los arcos descargan su fuerza en columnas adosadas a los pilares rectangulares, o a los muros laterales del templo. Los pilares también sirven de apoyo a los arcos formers.

Todos los arcos se apoyan en columnas, los capiteles de las cuales están esculpidos. Podemos ver tres grandes grupos: vegetales, animales y historiados. El primer grupo son los más abundantes, dónde podemos ver una gran variedad de motivos vegetales, algunos de factura muy tosca y otros más refinados.

Dentro de los capiteles animales podemos ver aves como lechuzas, pelícanos, palomas o águilas, otros animales como serpientes, lobos o leones así como un amplio abanico de animales fantásticos.

En el grupo de los capiteles historiados encontramos numerosas escenas bíblicas como la del Pecado Original, la expulsión del Paraíso o la Epifanía. También se representan algunos pecados como la avaricia y la lujuria.

En la intersección del transepto y de la nave principal se levanta un cimborrio, de planta octogonal y cubierto por el interior con una cúpula semiesférica.

Cuatro ventanas permiten el paso de la luz del sol. Estos están decorados con dos arquivoltas, de bisel la más exterior y de baquetón la interior. Esta se apoya en dos columnas con los capiteles esculpidos. Rodea el conjunto un guardapolvo ajedrezado. El mismo motivo escultórico lo encontramos en una línea de imposta, que recorre los muros a la altura del arranque de los arcos de las ventanas y en la cornisa que hay bajo el tejado. Esta se apoya en canecillos esculpidos. En los muros dónde no hay una ventana, encontramos una columna adosada, que llega hasta la cornisa

El mismo tipo de ventanas que vemos en el cimborrio se encuentran también en los muros laterales del templo, un en cada uno de los tramos de la nave, a excepción de los tramos dónde hay una puerta.

Dos líneas de imposta recorren los muros laterales, una por debajo del nivel de las ventanas y la otra en el punto de arranque de los arcos de las mismas.

Se accede al templo por cuatro puertas. Las que encontramos en los muros laterales son originales, mientras que la del brazo sur del transepto no está claro si fue añadida durante la restauración del templo o bien ya existía con anterioridad. En este sector se adosó una sacristía, que posteriormente fue demolida.

Tampoco es original la puerta que hay en la fachada oeste, totalmente reconstruida en la última restauración. Los estudiosos no se ponen de acuerdo en sí ya existía o bien fue "inventada" a imitación de las otras dos.

Las tres están construidas en un cuerpo añadido. Están formadas por tres arquivoltas de medio punto, protegidas por un guardapolvo ajedrezado.

La puerta norte tiene como particularidad que la arquivolta central se apoya en dos columnas con los capiteles esculpidos.

Las tres puertas tienen un pequeño tejaroz, que se apoya en nueve canecillos esculpidos.

En los ángulos del muro oeste encontramos dos esbeltas torres de planta circular. La del lado sur fue reconstruida tomando como modelo la del lado norte.

Se accede a su interior por unas puertas que hay en los ángulos de la iglesia. En la del lado norte podemos ver un tímpano decorado con un crismón. Por su factura se cree que es anterior al resto del templo y por lo tanto fue reutilizado.

En el ábside podemos contemplar una talla de Cristo Crucificado de finales del siglo XIII.

Lo acompañan una talla de San Martín del siglo XIV y una de Santiago del siglo XVI.