El Palacio es del siglo XV y fue quemado en 1521 por los Comuneros. Perteneció a los Velasco que fueron Condestables de Castilla.
El castillo de Los Velasco fue la residencia de los Condestables durante el siglo XV, en este mismo siglo, los Comuneros incendiaron el edificio, destruyéndose casi en su totalidad, pero sobre las ruinas, el Condestable Iñigo I, construyo un nuevo palacio .
Contaba con unas enormes murallas que tenían un foso de 60 pies de ancho y 40 de profundidad. Dentro de ellas, el espacio se repartía en 3 pisos y varios subterráneos.
Del primitivo castillo del siglo XII, cuyos muros estaban construidos sobre una planta cuadrada, en parte de sillería y en parte de tierra y canto rodado, hoy se conservan las ruinas que nos dejó el último asedio que sufrió el palacio en el siglo XVIII.
Conserva 2 de sus lienzos, aunque en muy mal estado, pudiéndose observar sus ventanas, algún tramo de escaleras y los mechinales de sus pisos. En la esquina de estos 2 lienzos, se ve una torre circular “El Cubo del Palacio”, de 2 alturas, que en sus tiempos albergaba la prisión en su interior y en cuyo interior en la actualidad se encuentra el deposito del agua.
De los 2 recintos amurallados que tuvo Villalpando quedan los restos del primero de ellos debió de erigirse en tiempos de Fernando II de León, en la segunda mitad del siglo XII y era de planta rectangular y ligeramente ovalado hacia el suroeste. Este muro defensivo se dirigía al castillo y desde aquí, cerrando la villa por el noroeste, hacia la plaza Yeguarizo.
El segundo recinto, de forma ovalada, fue construido en la Baja Edad Media y quedan vestigios en las inmediaciones de las puertas de Santiago y San Andrés.
Es en el S XVIII cuando los Condestables son privados de la Condestablía y de la posesión de su distinguida casa y estados. Todo esto ocurre por el triunfo de Felipe V contra el Austriaco en 1711, de esta manera los Condestables, que habían apoyado al austriaco, abandonan definitivamente el palacio-alcázar y se trasladaron por siempre a la corte. Fue en el año 1727 justamente dos siglos después de haberse reedificado dicho palacio, amenazando ruina su techumbre, fue desmantelada.
Hoy tan sólo queda del edificio las cuatro paredes en parte derruidas y el cubo del oriente donde estuvieron presos los dos hijos de Francisco I Rey de Francia.