La fachada principal de la iglesia, situada a los pies, está cobijada por un pórtico de tres arcos apuntados; la puerta central es abocinada y se decora con dientes de sierra y una cornisa con modillones. En el hastial hay un gran rosetón, magnífica composición de elementos góticos y mudéjares. Por encima se alza una pequeña hornacina con imagen de San Lorenzo, del siglo XIV.

La iglesia es de planta rectangular, formada por tres naves que se cubren con armaduras de madera de estilo mudéjar. La cabecera está formada por triple ábside, poligonal el central y planos los laterales. La capilla mayor y los ábsides laterales se cubren con bóvedas de crucería gótica. En el interior de la capilla mayor se conserva una de las mejores muestras de pintura italogótica de Andalucía, realizada al fresco en la segunda mitad del siglo XIV.

En la zona alta se desarrollan siete escenas mostrando el Beso de Judas y el Prendimiento, las Injurias de los Soldados, Jesús camino del Monte Calvario, la Crucifixión, el Descendimiento, el Entierro de Cristo y la Resurrección, realizadas en el segundo tercio del siglo XV. Las bóvedas están pobladas de serafines, que llenan cada uno de los plementos, con caracteres aún más italianizantes, también realizadas por diversas manos.

En la capilla del Sagrario hay un retablo de mediados del siglo XVI, formado por un cuerpo con hornacina enmarcada por columnas corintias y entablamento con segmentos de frontón con figuras recostadas de la Esperanza, la Justicia y la Fe. En él se venera la talla del Señor de la Humildad, de comienzos del XVII.

En la mitad de la nave izquierda se encuentra un retablo barroco con columnas salomónicas, de hacia 1720, que luce en la hornacina central la imagen coetánea de la Virgen de los Remedios y en el nicho del ático la de San Fernando. A ambos lados, grandes lienzos del siglo XX que proceden de la ermita de San Juan de Letrán.

La antigua capilla de la Magdalena está hoy dedicada al Cristo del Remedio de Ánimas. Es de planta cuadrangular, cubierta con bóveda de arista gótica que apoya sobre capiteles de tipo ménsula. La imagen del titular es obra anónima del siglo XVII, de taller granadino. En un lateral está la Virgen de las Tristezas, imagen de candelero barroca del siglo XVIII, procedente de Écija (Sevilla). Sobre el muro cuelgan pinturas del siglo XVIII que formarían parte de un ciclo histórico de la vida de la Virgen María y representan la Visitación, los Desposorios y el Nacimiento.

Preside el presbiterio una imagen de San Lorenzo, talla en madera policromada, de indudable estética barroca, que procede de un retablo lateral del templo.

La Virgen de Villaviciosa, obra labrada en 1974 para albergar en su interior la primitiva imagen, preside en un manifestador barroco la Capilla del Sagrario.

En el ábside de la nave izquierda se hallan actualmente las imágenes titulares de la Cofradía de Nuestro Padre Jesús de los Reyes en su Entrada Triunfal en Jerusalén, María Santísima de la Victoria y Nuestra Señora de la Palma. La primera fue tallada por Juan Martínez Cerrillo en 1963 y tranformada totalmente por Miguel Ángel González Jurado en 1993. Por su parte, la Virgen de la Victoria es una talla de candelero del siglo XVIII, restaurada por Francisco Romero Zafra, que procede del desaparecido convento de Nuestra Señora de las Huertas. La Virgen de la Palma, también de candelero, fue realizada por Romero Zafra en 1990, siendo retocada recientemente por su propio artífice.

El ábside de la nave derecha está cubierto por un retablo barroco realizado entre 1768-1770 por Juan Morillo y dorado entre 1783-1785 por Francisco de Cobaleda. En la hornacina central se halla la imagen de Jesús del Calvario, obra de Fray Juan de la Concepción, bendecida en 1724. El San Roque del ático es de mediados del XVIII.

La Virgen del Mayor Dolor, obra de candelero, fue realizada por los imagineros Díaz Jiménez y Castillo Ariza en el año 1945. Fue profundamente restaurada en 1992 por Miguel Ángel González Jurado, quien de nuevo la retocaría cinco años más tarde como consecuencia de los daños padecidos por un incendio fortuito.

En la fotografía podemos observar, a la derecha, parte del ático del antiguo retablo mayor, realizado por Juan del Río y Francisco Hurtado en 1696, con lienzo central que representa un Calvario pintado por Fernández de Castro. A la izquierda, retablo de mediados del XVI, parejo al del Cristo de la Humildad -en el que antiguamente se veneraba al Sagrado Corazón de Jesús-, adornado con escudos en el banco y una cartela en la que aparece inscrito el año 1564. Alberga un lienzo del Descendimiento, copia de un original de Rubens, y en su frontón aparecen las figuras recostadas de la Fortaleza, la Caridad y la Templanza. Ambos se encuentran en la capilla lateral de la nave derecha, actual capilla del Sagrario.

El ábside izquierdo posee óleos sobre lienzo de interés como el que representa a la Virgen de las Angustias, fechado, al igual que el resto, en el siglo XVIII.

Detalle del campanario, dispuesto por Hernán Ruiz II (1555) junto con tres cuerpos decrecientes rematados por el santo titular, sobre el alminar de la antigua mezquita.