Aunque muy modificada durante los siglos XVIII y XIX, la iglesia presenta una estructura de claro estilo gótico mudéjar. Sus orígenes se remontan a la primera mitad del siglo XIV. De esta fecha es su planta de tres naves y la portada de arco abocinado. Más tarde, en 1559 se construyó la portada del muro derecho, levantándose en 1584 la actual Capilla del Cristo de las Penas.
En la nave de la derecha se encuentra una capilla con el Cristo de las Siete Palabras, obra de Jerónimo Hernández de fines del siglo XVI. De mediados del mismo siglo es la Virgen con el Niño, obra de Roque Balduque y Juan Giralte. En los bancos de los retablos laterales existen pinturas sobre tabla de Villegas Marmolejo de hacia 1590. Firmada en idéntica fecha y del mismo autor es la pintura sobre tabla de la Virgen de los Remedios.
Asimismo, es de buena factura un crucero de alabastro fechado en 1582 que se halla delante de la portada de la nave de la epístola. Interesante resulta la Alegoría de la Eucaristía, de Francisco de Herrera "el viejo", situada sobre la puerta de ingreso de la capilla sacramental.
En la cabecera de la nave de la epístola, existe una pintura de la Virgen de los Remedios, datable para algunos en 1545 y cercana a la obra de Pedro de Campaña. En la Capilla de la Hermandad de las Penas, cuyos paneles de azulejos fueron realizados por Hernando de Valladares en 1602, se conservan los relieves del Descendimiento y de la Serpiente de bronce, realizados por Andrés de Ocampo en 1603. Muy interesante son las obras de Jan van Hemessen, que tanto debieron impresionar a Velázquez. Para finalizar, aunque un poco posterior a la partida de Velázquez a la Corte, en su sacristía se conservan, procedentes del primtivo retablo mayor, cuatro lienzos con escenas de la vida de San Vicente firmados y fechados en 1636 por Francisco Varela.