Hace algunos años aparecieron en el pago de "La Encomienda" vestigios arqueológicos (cerámicas y una estela romana fechada en el siglo II y que actualmente se encuentra en el Museo Arqueológico Provincial de Palencia) que demuestran la existencia de una posible villa romana.
 

    La actual iglesia parroquial de Santa Coloma (o Columba) -declarada monumento histórico artístico en 1982-, conserva vestigios del siglo XIII, aunque sería reconstruida en los siglos XV y XVI con elementos góticos y renacentistas. Consta de tres naves, separadas por pilares, con tres ábsides poligonales.

    En su interior destaca el retablo mayor (siglo XVI), la pila bautismal románica y las bóvedas ojivales de la sacristía.
 

En el siglo XIV se la conoce como "Villa Mediana" y estaba amurallada. Uno de sus portillos es similar al de Dueñas  y también alberga en su torre una pequeña ermita.     En el alto conocido como el Telégrafo existió una torre de señales del telégrafo de espejos.     La tradición cuenta que, el origen del nombre de Villamediana, se debe a la opinión que le mereció el lugar al ser visitado por rey Alfonso VI, el cual, al llegar al pueblo y ver que no salía nadie a recibirle, dijo: «esto más que una ciudad, es una villa y mediana».

    La toponimia nos dice que el nombre de la villa significa, «la villa situada en el medio» de otras dos.