Nos encontramos con uno de los templos más enigmáticos del románico español. Su parecido con la mezquita de Omar, sede de los templarios en Jerusalén y posible antiguo templo de Salomón, y con otras edificaciones templarías de la península como la iglesia de Tomar en Portugal o las del Santo Sepulcro o Nuestra Señora de Eunate en Navarra ha hecho que durante mucho tiempo se haya atribuido su construcción a este orden.  Las últimas investigaciones se inclinan por la tesis que sus fundadores fueran los caballeros del Orden del Santo Sepulcro. En 1531 esta orden se unió a la de San Juan de Jerusalén, actuales propietarios del templo. 

La fecha de su construcción, en cambio, no ofrece ningún tipo de duda gracias a una lápida que encontramos en el interior del templo, donde se indica que fue el 13 de abril de 1208. En aquel momento se consagró el templo al Santo Sepulcro.

Tiene planta poligonal de doce lados, en tres de los cuales se abren unos ábsides semicirculares.  Posteriormente se añadí un cuarto ábside que realiza las funciones de sacristía.

En uno de los lados también encontramos la torre campanario, de planta cuadrada. Originariamente eéta se construyó separada del templo, al estilo de los campanarios italianos de la época, pero posteriormente se volvió a edificar una torre, esta vez adosada al templo. De la primitiva torre todavía se pueden ver fragmentos de sus muros justo enfrente de la actual. Se desconoce el motivo del cambio de ubicación del campanario, lo más probable es que el primero se derrumbara.

Exteriormente el templo se caracteriza por su sobriedad. La magia y la grandeza la encontramos en el interior. Una vez atravesamos la puerta de acceso nos encontramos que todo el templo se organiza alrededor de un habitáculo central, también poligonal de doce caras. En las aristas encontramos columnas adosadas que tienen los capiteles esculpidos con motivos vegetales y geométricos. Estos sirven de sustento a unos arcos fajones radiales, que refuerzan la bóveda de cañón con que se cubre el templo.

La estancia central está dividida en dos pisos. El inferior es de reducida altura a modo de cripta. Podemos ver los capiteles, donde se apoyan los dos nervios de la bóveda, casi a ras del suelo. Tiene una puerta en cada uno de los puntos cardinales, mientras que en los otras lados encontramos un arco ciego en el muro exterior.

Gracias a una doble escalera se accede al piso superior, lugar dónde todavía hoy los Caballeros del Orden de Malta celebran sus ritos litúrgicos. Se cubre con una cúpula que se apoya en dos parejas de arcos, similar a la que vemos en la iglesia de San Millán de la misma ciudad.

En el centro de la sala encontramos un altar. Está decorado con bajorrelieves dónde están esculpidos arcos apuntados que se entrecruzan y se apoyan en columnas con el fuste en zig-zag. Estos arcos nos recuerdan a los que podemos contemplar en el claustro de San Juan de Duero de Soria. Los laterales del altar están esculpidos con arcos de herradura que se sostienen gracias a columnas con el fuste liso.

Como en el caso del piso inferior, los muros exteriores de la sala están decorados con grandes arcos ciegos, pero que este caso son apuntados.

Se cree que sobre este piso todavía hay otro, en que habría una cámara secreta.

Todo el templo se caracteriza por la austeridad en la decoración. A pesar de todo, todavía se pueden ver restos de pinturas murales del siglo XIII y también de épocas posteriores.

Los ábsides también destacan por su desnudez decorativa, que se limita a una arquivolta con columnas y capiteles esculpidos en las ventanas y a los capiteles de los arcos triunfales.

En el ábside central encontramos una talla del Cristo Crucificado, que data del siglo XIII.

En el del lado derecho encontramos la imagen de la Virgen de la Paz. Es una talla románica realizada en piedra.

Si nos acercamos al ábside izquierdo podremos contemplar la arqueta dónde se guardaba la reliquia de un fragmento de la Cruz de Cristo, que da el nombre al templo (Vera Cruz).

Posteriormente, en el siglo XVI, se habilitó una capilla en la base de la torre campanario, en que se veneraba esta reliquia.

Se accede al templo por dos puertas. La principal está en el muro opuesto al ábside principal, al oeste. Está formada por cuatro arquivoltas decoradas con dientes de sierra, que se apoyan en tres parejas de columnas con los capiteles esculpidos, donde se pueden ver guerreros luchando, arpías y unas bestias llevándose a un pecador. En el tímpano, que es liso, ha pintada una cruz roja. A ambos lados de la puerta también encontramos dos cruces de Malta pintadas. 

Corona la portalada un tejaroz apoyado en canecillos esculpidos, alguno de ellos muy deteriorado.

La otra puerta está junto a la torre de campanario. Es el actual acceso al templo. Presenta una estructura más sencilla que la del lado oeste. Está formada por cuatro arquivoltas que se apoyan directamente en el muro o en dos pares de columnas con los capiteles esculpidos con motivos vegetales, animales y algunas figuras humanas. Sobre la portalada se pueden distinguir unas esculturas que representaban a las mujeres que fueron a ver el Sepulcro de Cristo. Ante ellas un ángel y el sepulcro vacío. El grado de erosión hace difícil su interpretación.