En el año 875 Alfonso III repuebla el lugar de Dueñas y construye o restaura el castillo que se levantaba sobre un pequeño cerro, en una posición estratégica cercana a la confluencia de los ríos Carrión y Pisuerga desde la que se controlaba el camino que desde Simancas atravesaba el valle del Pisuerga. Apoyado por las fortalezas de Tariego, Magaz y Cevico de la Torre dominaba una amplia zona del Cerrato.

Sobre el año 984 es vuelto a destruir por Almanzor en una de las expediciones por tierras cristianas.

Aparece en 1127 en la donación real al Cid como "Castro de Donnas", para a mediados del siglo estar a cargo de Fernando Rodríguez de Castro, descendiente del conde Pedro Ansúrez. En 1160 figura Nuño Pérez de Lara, en poder de cuya familia estaba cuando Alvaro de Lara, a la muerte de Enrique I, se enfrenta a Fernando III y su madre doña Berenguela que tienen que tomar el castillo a la fuerza.

De nuevo la fortaleza es asediada a finales del siglo XIII, en la guerra de sucesión durante la minoría de edad de Fernando IV, y a pesar de ofrecer la regente María de Molina al concejo de Palencia la villa y castillo de Dueñas si lograban tomarlo, no lograron conquistarlo.

En 1367, durante la guerra fratricida entre Pedro I y Enrique II de Trastámara, la defensa de la villa y el castillo estaban bajo el mando del adelantado de Castilla Rodrigo de Torquemada. No obstante tras un mes de asedio en el que se utilizaron sofisticadas máquinas de guerra son tomados por Enrique II, quien los cede a su dama de honor Leonor Álvarez.

Aprovechando la Guerra de las Comunidades en 1520, la población se levanta contra Juan de Acuña, Conde de Buendía, tomando el palacio y haciendo prisioneros a los condes, de los que se valen para que el alcaide entregue la fortaleza.

El castillo estaba al nordeste de la población, sobre un pequeño cerro que alcanza los 852 metros de altura. Estaba rodeado en la parte inferior del cerro por un profundo foso del que aún se conservan restos, especialmente en los frentes Norte y Sur. Por encima de él, a media altura, existe una terraza de unos 12 metros de ancho que debió estar protegida por un muro del que quedan escasos vestigios en el frente Norte.

Al Sudoeste se conservan unos restos que pudieran corresponder a una puerta de acceso. El trozo de lienzo más grande que se conserva, se encuentra al Oeste, mide 6 metros de largo y presenta varias hiladas de piedra hasta alcanzar una altura máxima de 1,60 metros. En la cima hay una explanada de 7 por 18 metros donde pudo estar emplazada una torre o atalaya.

Existe un grabado de Dueñas, realizado por Robert Pollard en 1808, en el que se ve el castillo al fondo. Según dejó escrito en 1845 Richard Ford, tenía planta rectangular, aunque en esta época ya estaba arruinado, a lo que ayudó el que desde 1829 se permitiera la utilización de las piedras de la muralla y del castillo para la construcción del Canal de Castilla. Años después también se autorizó para su uso particular a los vecinos.