La Muy Noble y Leal Villa de Palenzuela se sitúa en una posición estratégica en la margen derecha del río Arlanza, próxima a la confluencia con el río Arlanzón. Se tienen referencias de su ocupación desde tiempos prehistóricos. En época prerromana era la importante ciudad vaccea de Pallantia.
Sitiada por los generales romanos Lúculo (151 a.C.), Lépido (137 a.C.), Carpurnio Pisón (135 a.C.) y Pompeyo (74 a.C.) es finalmente conquistada y arrasada por este último en el año 72 a.C. y no vuelve a ser ocupada hasta el siglo I, momento en que ya había sido fundada la Pallantia romana, la actual Palencia.
Palenzuela fue capital de un alfoz de 38 pueblos y más tarde cabeza de la Merindad del Cerrato. En el año 850 ya se menciona su castillo, lo que no fue obstáculo para que en el 919 fuera saqueada dos veces por las razias árabes.
Los primeros señores de la villa fueron los condes de Castilla, posteriormente pasó a los reyes de Castilla. Dotada de fueros a finales del siglo X por el conde Don Sancho, nieto de Fernán González, son confirmados y ampliados por varios monarcas.
En tiempo de Fernando III es señorío de Alvaro Núñez de Lara, que enfrentado al rey y a su madre Doña Berenguela, lo pierde tras caer derrotado ante las tropas del monarca. Pasa el control a la Corona y en 1219 es entregado en arras a la futura reina Beatriz, junto con otras localidades, entre las que figuraban Ampudia, Astudillo y Carrión en la provincia de Palencia.
En 1295 es señorío de Juan Núñez de Lara, quién se rebela contra María de Molina, regente durante la minoría de edad de Fernando IV, por lo que la villa es sitiada y asediada durante seis meses. Tras su toma vuelve de nuevo a la Corona.
La localidad, incluida en el obispado de Burgos, aparece en 1352 como señorío de la madre de Pedro I, la reina Doña María, y de todos los derechos de la villa, que es cabeza de la merindad del Cerrato. Los vecinos pagaban martiniega, servicios, monedas, yantar e infurción, aunque no fonsadera.
Pedro I "El Cruel" al sublevarse la villa, la sitia personalmente en 1356, logrando la rendición a las tropas leales a cambio del perdón. Entrega el señorío a María de Padilla. En 1405 pertenece a la reina Catalína, esposa de Enrique III.
En septiembre de 1425, Juan II convoca Cortes en Palenzuela. Estas tienen lugar en el convento de San Francisco que se encontraba extramuros de la villa, y coinciden con el momento de máximo esplendor de la población. Cuatro años más tarde pasa a los Almirantes de Castilla por permuta con la villa de Arcos de la Frontera. Más tarde, en 1444, es lugar de enfrentamiento entre los reyes Juan II de Castilla y Juan de Navarra.
Alonso Enríquez de Quiñones señor de las fortalezas de Palenzuela, Hornillos y Cordovilla la Real, junto con su cuñado Juan de Tovar, que posee la de Astudillo, se sublevan en 1451 contra Juan II y su favorito Alvaro de Luna. Asediada la villa con artillería, se rinde en enero del año siguiente. El rey entrega Palenzuela a su hijo Enrique, volviendo de nuevo a los Almirantes de Castilla en 1454.
Aparece el censo realizado en el siglo XVI con 364 vecinos pecheros. La localidad es cabeza del arciprestazgo de Palenzuela y según datos eclesiásticos contaba con 500 vecinos.
En la guerra de la Independencia, es ocupada en varias ocasiones por las tropas francesas, que tenían su cuartel general en la vecina localidad de Quintana del Puente. En 1813 el mariscal Soult se apropia del palacio de los Jalón, lugar donde pasa noche José Bonaparte cuando más tarde abandona el país.
A mediados del siglo XVIII el núcleo urbano estaba formado por 236 casas, alguna de buena construcción, para una población de 236 vecinos, equivalentes a 1.227 almas.
