Existen vestigios desde la época prehistórica pasando por una época romana de gran esplendor, reflejada en las villas romanas de La Olmeda cerca de Saldaña, o La Tejada en Quintanilla de la Cueza.
Con los visigodos llegó una de las etapas de mayor esplendor para la ciudad, pues la constituyeron en sede de la corte, además que desde el siglo IV también era sede episcopal de relieve (se dice que su diócesis era la más importante de España tras la Toledana). Quedan restos del vestigio visigodo en la Cripta de San Antolín (que es la actual cripta de la catedral) y en la cercana localidad de Baños de Cerrato con su iglesia de San Juan de Baños (siglo VII), situada a tan solo 7 km de la capital que está considerada la obra cumbre de la arquitectura visigoda.
Posteriormente la provincia fue fruto de conflictos permanentes por su condición de frontera entre el reino de León y el de Castilla. Uno de los hitos más remarcables de la historia de Palencia se dio durante el siglo XIII, con la fundación de la primera universidad de España y una de las primeras del mundo.
