Resultado de un largo proceso constructivo, la iglesia se edificó probablemente sobre otro templo anterior dedicado a la misma advocación en lo que pudo ser el patio de armas de la antigua fortaleza. Dos de las cuatro torres de este castillo se conservan adosadas a la fachada occidental de la iglesia.
El templo presenta planta de cruz latina de una sola nave con crucero, cuatro capillas-hornacinas a cada lado y coro a los pies. En el interior destacan la cubierta de bóveda de cañón con lunetos y las capillas laterales que se abren a la nave principal mediante arcos de medio punto, sobre los que se apoya una cornisa que recorre todo el inmueble.
El crucero, escasamente desarrollado al exterior, tiene cuatro arcos torales sobre los que se sustenta una cúpula de media naranja sobre pechinas decoradas con medallones entre los que se representan las figuras de los Evangelistas. El programa decorativo de la Iglesia de San Andrés se completó en el siglo XVIII en estilo barroco con la instalación del retablo del altar mayor y la sillería del coro.
RETABLO MAYOR
El retablo mayor presenta en el primer cuerpo dos pinturas de San Pedro y San Pablo realizadas por el artista local Moisés Bueno, un frontón semicircular presidido por la imagen de un crucificado e, insertas en los vanos centrales del segundo cuerpo, otras dos pinturas de San Juan Bautista y San Sebastián, además de una intensa decoración con temática vegetal y placas doradas.
El coro, ubicado a los pies del templo y elevado mediante gradas respecto a la nave, se organiza en dos pisos con 27 asientos en el superior y 18 en el inferior. Los respaldos están tallados con motivos florales y con la figura de San Andrés en el sitial de honor.
En el exterior destacan la portada principal de la fachada sur, de estilo clasicista, gran sencillez y escasa decoración, y la fachada oeste donde se insertan las dos torres medievales. De ellas, la que se sitúa esquinada con la fachada norte domina en altura y alberga el campanario.
La Iglesia de San Andrés se caracteriza por su gran volumen. Aunque emplazada en el corazón de la ciudad vieja de Villanueva del Arzobispo, se aprecia desde una extensa área más allá de los límites urbanizados. Para preservar su adecuada percepción visual, el decreto de inscripción en el Catálogo del Patrimonio Histórico establece un amplio entorno de protección que incluye inmuebles y espacios públicos y privados de las calles Puerta Hombría, Puerta del Sol, Iglesia, Arquillos, Platerías, Palacio, Costanilla y Corredera.
