Al igual que otras localidades del Cerrato, es repoblada a partir de finales del siglo IX, aunque varios restos arqueológicos que han aparecido en el término municipal indican la probable existencia de una villa romana anterior.
En el siglo XIV se la menciona con el nombre de “Villa Mediana”. Bajo el reinado de Alfonso XI eran vasallos del hijo bastardo del rey don Pedro de Aguilar.
A mediados de siglo en el libro Becerro de las Behetrías figura como lugar de behetría de don Nuño, y son naturales los Lara, Vizcaya, Torquemada, Itero y Villamediana. Dan por martiniega al rey 382 maravedís y otros 130 por el barrio de San Pedro situado cerca de Reinoso que se encuentra despoblado, además de 160 a don Nuño y 78 al adelantado. Pagan monedas, servicios y 60 maravedís por yantar, además de 25 maravedís al merino del rey.
También pagan yantar a don Nuño cuando viene a la localidad y 6 maravedíes a los Lara y Vizcaya.
En 1475 le corresponde pagar 43.982 maravedís de la contribución que Isabel la Católica impone a los pueblos la merindad de Cerrato.
El Emperador Carlos V permanece varios días de 1527 buscando entretenimiento y descanso por los pueblos palentinos, pasando el día 26 de septiembre en Villamediana, lugar por el que vuelve a transitar el 10 de octubre ya camino de Burgos. Por esa época la población cuenta con 221 vecinos pecheros.
En 1571 Felipe II otorga las localidades de Villamediana y Valdeolmillos al marqués de Poza a cambio de las salinas de Poza que el rey incorpora al patrimonio real. Al enterarse de la situación, ambas villas acuden al Consejo de Hacienda con el fin de paralizar la venta, comprometiéndose los ayuntamientos a aportar una cantidad para continuar perteneciendo a la Corona.
Para hacer frente al pago deben endeudarse de tal forma que en 1599 Villamediana reconsidera su decisión y obtiene de Felipe II licencia para vender su jurisdicción, alcabalas y rentas jurisdiccionales y así recuperar los censos que ha tomado en 1588. En esos once años la villa se ha despoblado pasado de 450 vecinos a 300 en 1599. Entremedias, en 1591, hay 394 vecinos, de los que 383 son pecheros y 11 clérigos, con total ausencia de hidalgos.
El 25 de enero de 1600 la localidad se vende a Juan de Tassis, Correo Mayor del Reino, por 20.608.320 maravedís, sin que se haga cargo de la deuda acumulada que la villa tiene de réditos impagados. Tres años más tarde Felipe III le otorga el Condado de Villamediana.
La villa cuenta en 1631 con 330 vecinos, 1.060 personas, además de 160 cabezas de ganado mayor y 2.000 de ganado menor, y aunque tienen un contrato de suministro de sal de 116 fanegas anuales, solicitan sólo 80 para el año.
Según datos censales de 1712 hay 180 vecinos, entre los que se incluyen 22 viudas contadas como 11 vecinos, y 86 pobres. Hay también 11 mendicantes, mozos asalariados y algún vecino ausente que no se incluyen.
A mediados del siglo XVIII es villa de señorío del Conde de Oñate. Cuenta con una población de 260 vecinos, entre los que se incluyen las viudas computadas cada dos como un vecino y los clérigos. El caserío esta formado por 250 casas habitables, 3 inhabitables y 12 arruinadas.
En 1768 el número de habitantes asciende a 1.068 personas, de las que 537 son hombres y 531 mujeres. Tres años más tarde se sabe de la existencia de 7 cofradías en la localidad: de Ánimas, Santa Vera Cruz, San Sebastián, Nuestra Señora del Rosario, Nuestra Señora de los Esclavos, San Blas y la cofradía de Nuestra Señora del Corro y San Pedro, además de la congregación de Santo Tomás de Aquino. Todas celebran al menos una función y misa, además algunas dan refresco o limosna.
Datos de 1787 indican que la villa tiene como autoridad un alcalde ordinario, es señorío del Marqués de Montealegre, pertenece al partido de Cerrato y a la intendencia de Palencia. La población es de 619 hombres y 627 mujeres para un total de 1.246 habitantes. Por ocupación se reparten entre 193 jornaleros, 41 labradores, 19 artesanos, 10 criados, 7 comerciantes, 6 militares, 4 estudiantes, 1 escribano y 1 fabricante. Además eclesiásticos hay 8 beneficiados, 2 tenientes de cura, 1 sacristán y 1 de la orden tercera.
En 1828 se indica la existencia de 393 vecinos, 1.288 habitantes, y en 1843 datos oficiales censan 252 vecinos de los que 156 son electores. Dos años después se indican 1.210 habitantes, equivalentes a 280 vecinos. Además de la agricultura y ganadería en la localidad se fabrican medias de lana.
A mediados de siglo la población asciende a 240 vecinos, equivalente a 1.248 personas, con un casco urbano con 280 casas calificadas de mala construcción que están distribuidas en 4 barrios.
La villa cuenta en 1874 con 1.162 habitantes y el casco urbano con 271 casas. Hay además 110 bodegas. Tres años más tarde la población de derecho la forman 1.052 personas, 532 hombres y 520 mujeres.
Villamediana fue villa amurallada de la que a mediados del siglo XIX apenas quedaban señales. Sólo se conserva una puerta de sillería que presenta un arco de medio punto al exterior. Tenía situados los portones en la mitad del pasillo de entrada, de unos 6 metros de largo, que se cubría con una cubierta de madera, sobre la que actualmente existe una pequeña ermita bajo la advocación de La Virgen de los Esclavos o "La Esclavina".
Algunos vecinos recuerdan que existió otra puerta, de aspecto similar, que se derribó en 1928 que probablemente corresponda con la que muestran las fotografías de la colección Ruiz Vernacci en las que aparecen tanto la puerta como la iglesia parroquial al fondo. En las imágenes se observa que se diferencia de la puerta de “La Esclavina” en que el arco de entrada es apuntado. Pudo estar ubicada en el cruce de la calle Clemente González con Arrabal del Portillo y la travesía del Portillo.
Una escritura de reparto de los bienes de Juan García de Padilla fechada en 1351 menciona la casa fuerte que este tenía en la localidad que es excluida de la asignación.
Dentro de su término municipal, en el alto del Telégrafo con 882 metros de altura, se situó una torre del telégrafo óptico, similar a la ubicada en Tariego de Cerrato con la que se comunicaba visualmente. La instalación en el mismo lugar de un centro de transmisiones del ejército, hace ya tiempo abandonado, provocó que desaparecieran los restos de la torre, que se encontraba arruinada.
Llama la atención al acercarse al pueblo la grandiosa silueta de la iglesia parroquial de Santa Columba que sobresale por encima de las casas. Construida en el siglo XIII con estilo románico, fue reconstruida posteriormente en los siglos XV y XVI con elementos góticos y renacentistas. También destacan es su casco urbano buenas muestras de arquitectura tradicional.