La primera noticia documental de esta Iglesia aparece en un documento del Cabildo de la Colegiata del año 1177, aunque su calificativo indudablemente permite suponer una cronología anterior. Tal vez el templo albergara provisionalmente, mientras se construía la Iglesia Mayor, al Cabildo de la Colegiata, pasando posteriormente a ser utilizada como capilla privada del Palacio Condal de D. Pedro Ansúrez, fundador de Valladolid.

Esta Iglesia primitiva del Siglo XI o anterior fue completada con la construcción, durante el primer cuarto del siglo XIII, de una torre monumental, colocada al oeste y un pórtico adosado a su muro norte, que serviría de mirador sobre el río Esgueva que durante mucho tiempo pasó junto a sus cimientos. La Iglesia primitiva se sustituyó, tal vez durante el reinado de Alfonso XI, en el Siglo XIV por una construcción gótica cuya estructura, excesivamente restaurada, es la que ha llegado a nuestros días.

Un templo en cuya planta no existía una perfecta regularidad debido al pie forzado con que se construyó, era lógico que sufriese las consecuencias de las continuas reparaciones, sintiéndose amenazado de ruina total. Para contenerla incluso se lanzó un arco-tirante en la nave central, se reforzaron sus contrafuertes, la torre se reforzó en su primer cuerpo y se hicieron otros muchos arreglos. Así en los inicios del pasado siglo hubo de ser restaurada "in extremis", para salvarla de la ruina a la que se veía abocada.

La declaración del templo como Monumento Nacional el 11 de Mayo de 1897, determinó afrontar la salvación de la torre y del pórtico románico. Posteriormente se logró la restauración total del edificio, que fue desmontado íntegramente, a excepción de su cabecera.

Según consta en diferentes documentos, trabajaron en la iglesia, entre otros, D. Diego de Riaño, D. Juan de la Lastra y D. Rodrigo Gil de Hontañon.

Su torre, apodada como "La Reina de Castilla", dividida exteriormente en cuatro cuerpos y rematada en esbelto chapitel apiramidado, es uno de los más bellos ejemplos de torre conservados en Castilla. El primero de los cuerpos, que abarca casi la mitad de la altura total, es liso y se halla únicamente perforado por un vano de medio punto sobre columnas. Los tres restantes cuerpos se encuentran perforados con ventanas en sus cuatro caras. Los arcos del tercer cuerpo se decoran con el motivo denominado cabeza de clavo o puntas de diamante que vuelve a  aparecer en las arquerías del pórtico. La torre, finalmente, se remata con cubierta piramidal con teja en forma de escama, del mismo tipo que la que debió poseer la Colegiata.

El pórtico o claustro, de gran austeridad ornamental, responde al conocido modelo de galería porticada característico de los templos románicos castellanos, si bien en este caso no se encuentra orientado al sur, como es lo habitual, sino al norte, explicable por el hecho de que el río Esgueva discurría por ese lado, por lo que serviría e mirador. Consta de un cuerpo rectangular con tres secciones de arquerías delimitadas por estribos, y dos puertas de acceso, una al este y otra al oeste. Las arquerías son del mismo tipo que las de las ventanas del tercer cuerpo de la torre, es decir, de medio punto decoradas con cabezas de clavo. Apoyan en columnas triples de esbelto fuste y con capiteles vegetales de tipo cisterciense.

La Iglesia tiene tres naves, la central más ancha, separadas por pilares fasciculados y cubiertos por bóvedas de crucería. Sus respectivos ábsides aparecen rasgados por grandes ventanales apuntados. El coro, construido en 1512 por D. Juan del Pozo y D. Juan de la Cantera, se sitúa a los pies y en alto, sobre bóveda que fue de crucería estrellada.

El resto de la Iglesia correspondería a una reconstrucción que se lleva a cabo en el siglo XIV, durante el reinado de Alfonso XI, perteneciendo ya al estilo gótico. Así, el interior la cabecera y la portada son de ese estilo. Se emplean arcos apuntados, arbotantes, contrafuertes que se rematan con pináculos, cresterías de rosetones delimitando los tejados de naves y ábsides, etc.

El interior se ilumina a través de rosetones, mientras que en la cabecera las vidrieras adoptan forma de ventanas geminadas rematadas con rosetones en el vértice en el arco apuntado.

Lamentablemente, con motivo de la restauración de la Iglesia, su interior perdió la mayor parte de las obras artísticas que la alhajaban, especialmente el magnífico retablo mayor, obra de mediados del siglo XVI realizada por el gran escultor Juan de Juni, que paso en 1922 a la Santa Iglesia catedral, y donde se encuentra en la actualidad.