La primera noticia escrita sobre esta parroquia es del año 1367, hace 649 años.
Pero el actual edificio comenzó a edificarse a principios del sigloXVI, hace, pues, quinientos años.
Contribuyeron a su construcción durante ese siglo, sobre todo, las 173 familias, o vecinos censados, que residían entonces en Villamediana, con el párroco y los nueve clérigos que le ayudaban en la parroquia. Según los datos del censo del año 1591.
La dirección de las obras corrió, como muestra la solidez y belleza del edificio, a cargo de buenos arquitectos, que los ingeniosos escultores retrataron en la piedra, junto a la gente común y a los hidalgos (13, según el censo) que componían la parroquia.
Los fieles de Villamediana, se agrupaban en varias cofradías, que fomentaban la piedad y devoción hacia Cristo, a la Virgen, a los Santos, y ayudaban a los hermanos necesitados, asistían a los enfermos y hacían sufragios por los difuntos.
Queda noticia escrita de las Cofradías de la Santa Vera Cruz, de Nuestra Señora de la asunción y la de Todos los Santos.
Así mismo hay constancia de varias Capellanías que ayudaban a que se mantuviera el culto divino, con la celebración de la Misa, celebraciones litúrgicas, fiestas y los aniversarios de los difuntos. Hay constancia de al menos 38 de estas capellanías.
La vida cristiana en la parroquia era fuerte y comprometida y nos legó un patrimonio, arquitectónico y escultórico en piedra, impresionante, al que los siglos no han deteriorado, sino embellecido y consolidado ¡COMPROMETEDORA HERENCIA!
Desde 1500 a 1808, además del párroco, bajo la autoridad del obispo de Calahorra, atendían la feligresía 9 sacerdotes, cuyo nombre y cargo aparecen en los censos de 1591 y de 1753.
Los escultores han reflejado en la piedra las gentes de la época (véase al que toca la guitarra) y hasta los difuntos que se enterraban en el suelo de la misma iglesia parroquial.
Los años 1750 en adelante, se sustituyendo las bóvedas de crucería de finales del gótico por las actuales de estilo barroco y se puso un gran retablo mayor de estilo barroco del que se conserva una dorada uva que da idea de su belleza. El actual retablo mayor, de estilo rococó de finales del siglo XVIII, fue traído en 1950 del pueblo soriano de Yanguas.
