En su término municipal se han encontrado restos de época romana de los siglos II y IV d.C. La primera referencia a la localidad se encuentra en un diploma falso del año 955, en la que aparece como "uilla Maurelli". Dos años más tarde se la menciona en un documento de donación.
Existe la creencia de que a principios de siglo XII estaba bajo el dominio de la Orden del Temple, aunque no existe ninguna prueba documental. El 29 de mayo de 1141 el rey Alfonso VII entrega la villa al obispo de Palencia Pedro II, desgajándola del alfoz de Dueñas, aunque manteniendo una comunidad de pastos con esta localidad.
En 1162 el obispo Raimundo II concede una "carta de buenos fueros", en la que se establece que cada vecino peche una serna al mes, la mitad de las caloñas y una infurción anual por un sueldo de valor.
A finales del siglo XII, en tiempos del obispo Arderico, se empieza a construir la iglesia de Santa María y, probablemente el palacio-fortaleza anejo, que en 1308 alojó a la reina María de Molina.
En el Becerro de las Behetrías, de mediados del siglo XIV, figura "Villa Moriel" como lugar del obispo de Palencia, al que pagan anualmente 540 maravedís en concepto de martiniega, 124 por yantar, 50 por otra yantar que llaman forzada y cada casa por fumazga 8 dineros, mientras el rey recibe otros 540 maravedís por martiniega, además de servicios, monedas y fonsadera.
El obispo Rodrigo Velasco muere en 1425 en el palacio a manos de un cocinero suyo que estaba loco. Años más tarde al obispo Pedro de Castilla, nieto del rey Pedro I, se le atribuye la construcción de la torre y gran parte del palacio e iglesia a mediados del siglo XV. En 1499 fallece el obispo Alonso de Burgos y en su testamento deja la cantidad de 50.000 maravedís para el reparo de la fortaleza de Villamuriel.
En el contexto de la Guerra de las Comunidades, el 14 de septiembre de 1520 varios vecinos de Palencia opuestos al señorío episcopal que ostenta Pedro Ruiz de la Mota, ante el rumor de que el alcaide de la fortaleza de Villamuriel la tiene prácticamente abandonada, se desplazan a esta localidad donde queman por completo el palacio, derriban parte de la torre y talan el cercano soto de Santillana.
Cuatro años después el obispo Antonio de Rojas perdona a los comuneros palentinos, obteniendo a cambio de la ciudad la cantidad de 925.000 maravedís por los daños causados durante la revuelta, dinero con el que reedifica la torre y el palacio episcopal.
Villamuriel cuenta con 86 vecinos pecheros en 1528. Años más tarde, en 1589, según datos eclesiásticos la villa es vicaría con 112 vecinos feligreses. Dos años más tarde se contabilizan 100 vecinos pecheros.
Según los datos del censo de la Sal confeccionado en 1631 la localidad cuenta con 42 vecinos, equivalentes a 121 personas, además de 57 cabezas de ganado mayor y 500 de menor. Inicialmente les asignan un acopio 60 fanegas de sal, cuyo importe a un precio de 50 reales la fanega es utilizado para el cálculo del importe a pagar por el servicio de millones. Tras reclamar por la cantidad de sal asignada, consiguen que se rebaje a 26 fanegas de sal, y por consiguiente que disminuya el cálculo de la cantidad a pagar.
El vecindario en 1712 lo forman 28 vecinos pecheros, 6 viudas contadas como 3 vecinos y 2 pobres. Hay además 1 mendicante que no tiene la consideración de vecino.
Según los datos del Catastro de Ensenada confeccionado en 1752, el número de vecinos asciende a 73, en el que se incluyen los eclesiásticos y 8 viudas, computándose estas últimas como medio vecino. El caserío está formado por 62 viviendas, aunque una inhabitable.
Con 478 personas aparece en el censo de 1768, de los que 247 son varones y 231 hembras. Están exentos del pago del pago de impuestos 6 personas por pertenecer al Real Servicio, 4 por ser de la Real Hacienda, además de 1 hidalgo, 1 de la Inquisición y 1 del Real Canal. Eclesiásticos hay 4 beneficiados, capellán, sacristán y 7 hermanos de órdenes regulares.
Tres años más tarde se sabe de la existencia de 3 cofradías: la Sacramental que celebra tres funciones anuales es la más importante; la cofradía de la Cruz celebra dos funciones y la de Ánimas una función de difuntos. Todas ellas celebran además diferentes misas. Los gastos anuales ascienden a 706,14, 360 y 67 reales respectivamente. Hay asimismo una congregación de "muchos vecinos" cuyas limosnas distribuyen en misas y refresco.
En 1787 la villa es de señorío episcopal del obispado de Palencia, incluida en el partido de Cerrato, intendencia de Palencia, con un Alcalde Ordinario como autoridad. Cuenta con 467 habitantes, 231 hombres y 236 mujeres, de los que con profesión específica hay 72 jornaleros, 23 labradores, 10 artesanos, 5 criados, 4 estudiantes, 2 hidalgos, 1 militar y 1 dependiente de la inquisición. Además hay 1 cura, 2 beneficiados, 1 sacristán y 2 acólitos.
Se tienen noticias de que en 1802 los prelados palentinos ceden la casa fuerte a la Parroquia de San Sebastián, hoy desaparecida. Durante la Guerra de la Independencia tuvo lugar en Villamuriel una batalla entre las tropas inglesas de Lord Wellington y el ejército francés, volviendo a usarse la iglesia como fortificación.
En 1828 se indica la cifra de 181 vecinos, 760 habitantes, de los que algunos se dedican a la panadería y las mujeres al hilado de estambre para las fábricas de mantas en Palencia. Según datos oficiales de 1843 figuran 110 vecinos de los que 85 son electores.
Con la Desamortización se fueron perdiendo poco a poco las dependencias palaciegas de la iglesia hasta llegar a la situación actual.
Pascual Madoz indica en 1850 una población de 108 vecinos, 562 almas, con 104 casas que califica de mala construcción y ayuntamiento que sirve de escuela de primeras letras a la que asisten 30 niños y 12 niñas. El censo oficial confeccionado en 1877 da una población de derecho de 1.159 personas, de las que 558 son varones y 601 hembras.
Diez años más tarde, la población asciende a 1.195 habitantes entre los que se incluyen los del lugar de Calabazanos. En pocos años se ha duplicado el número de edificios llegando a los 416, de los que 6 están habitados temporalmente y 179 inhabitados. También se han urbanizado algunas calles y se han renovado las casas del casco histórico.
La iglesia de Santa María la Mayor se sitúa en la zona más elevada del pueblo, es de estilo románico cisterciense y destaca la enorme torre adosada al templo que tuvo carácter defensivo del que aún se conservan en sus fachadas varios buzones. A finales del siglo XVI pierde su función militar al añadirse en la parte superior un cuerpo de estilo herreriano para servir de campanario. También se conservan en el ábside del templo tres garitas que carecen de almenas y en la fachada Norte los canecillos de un balcón amatacanado.
De las dependencias del palacio-fortaleza de los obispos, se sabe que se encontraban adosadas al Sur del templo, donde existen algunos vestigios. En la esquina Sudeste, formando parte de un contrafuerte, se encuentra el arranque de un arco formado por grandes dovelas, probablemente la entrada principal del palacio, junto a la que se encuentra una tronera de buzón para su defensa.
Además del templo, declarado en 1931 Monumento Histórico Artístico Nacional, se conserva un puente medieval sobre el río Carrión de once ojos del que se tienen referencias desde el siglo XIV. Junto a la localidad se encuentra la esclusa número 33 del Canal de Castilla, y en el pago de Soto Albúrez el conjunto formado por las esclusas 34, 35 y 36, con la peculiaridad de ser ovalada la primera y rectangulares las otras dos.