Realizada en tres fases, dos tardogóticas y otra clasicista, se comenzó hacia 1530 por Juan Campero, se continuó en 1560 con traza de Rodrigo Gil de Hontañón y se concluyeron estas fases por sus aparejadores Juan de Casares y Martín Ruiz de Chertudi en 1578, en que se tasó la obra. La segunda fase se empezó en 1589 por Felipe de la Cajiga respetando partes de la traza de Gil pero introduciendo elementos clasicistas, sobre todo en cubiertas y ventanas. En 1598 siguió su programa Juan de Nates.
Iglesia construida en piedra de grandes dimensiones. Tiene tres naves de cinco tramos a la misma altura según el tipo salón, crucero señalado, más capillas-hornacinas entre contrafuertes y presbiterio con capilla hemiexagonal. Se separan por gruesas columnas toscanas que reciben arcos formeros y fajones de medio punto de las bóvedas, éstas de cañón con lunetos construidas por Cajiga y Nates. Las de las capillas-hornacinas son de cañón casetonadas. Al exterior se aprecian dos fases; una goticista comprendida por la capilla mayor y los dos primeros tramos de las naves, con contrafuertes angulares que rematan en pináculos adosados y adornos de los símbolos de los Santos Juanes en cruces griegas, escudo de Carlos V y alfiz; el resto del edificio clasicista en el que se marcan los tramos por pilastras toscanas planas con ventanas geminadas en el cuerpo alto.
De las capillas destaca la de la Asunción, fundada por don Juan Gil de Nava, en el segundo tramo del lado del Evangelio, con inscripción y de mediados del siglo XVI. Es plateresca, de planta rectangular y cubierta en ochavo sobre trompas aveneradas con bóveda de crucería estrellada, con medallones en alto con los bustos de los Padres de la Iglesia, los santos Marcos y Mateo, Ezequías e Isaías y retablo de talla pintada de mediados de siglo. También es notable en el lado opuesto la capilla de don Pedro González (m. 1541), rectangular, de dos tramos cubiertos con bóvedas estrelladas tardogóticas, se abre a la nave por arco de medio punto, con retablo plateresco y esculturas del Maestro de San Pablo de la Moraleja. El coro, en bajo y a los pies, es obra de Juan de Nates; se decora con sillería barroca de Pedro Gamboa (h. 1711).
La torre se reconstruye a finales del siglo XVII por Juan de Revilla (en 1702 concluyen el chapitel Juan y Jerónimo Hernández). Gran sacristía realizada con trazas de Alberto de Churriguera y decorada con yeserías (1728). El atrio es de Andrés González de Cisniega (1625).
Interesante retablo mayor ensamblado por Francisco y Juan Velázquez (h. 1614), esculturas de Gregorio Fernández y policromía de Francisco Martínez (1623).
Bibliografía: E. GARCIA CHICO y A. BUSTAMANTE, Catálogo monumental de la provincia de Valladolid. Partido judicial de Nava del Rey, Valladolid, 1972; J.J. MARTIN GONZALEZ, Guías artísticas de España. Provincia de Valladolid, Barcelona, 1968; F. HERAS, Arquitectura religiosa del siglo XVI en la primitiva diócesis de Valladolid, Valladolid, 1975; A. BUSTAMANTE, La arquitectura clasicista del foco vallisoletano, Valladolid, 1983; A. CASASECA, Rodrigo Gil de Hontañón, Junta de Castilla y León, 1988.