Del antiguo castillo existente en la localidad no queda ni rastro, incluso se desconoce su ubicación exacta. Se sabe, a través de la evaluación de las obras que era necesario ejecutar en la muralla, realizada por el carpintero Juan Fernández y Alfonso Fernández Rabanillo en el año 1386, que se encontraba situada en el barrio de Gallegos, situado al noroeste del núcleo urbano, formando parte de la muralla, probablemente en la parte donde pierde su forma redondeada, junto a la Plaza de San Martín.
Alfonso Fernández de las Eras figura como alcaide de la fortaleza en el año 1401. Poco despúes, en 1408, dada la importancia que tenía el mercado semanal que se celebraba los viernes en la localidad, el concejo se dirige al infante don Fernando solicitando "carta de mercado" para que ese día los encargados del orden, incluido el alcaide del alcázar, no prendiesen a ninguna persona.
En 1428, la villa está en poder del rey de Navarra, que proyecta obras de fortificación en el alcázar, a lo que se oponen los vecinos mediante la colocación de cantos, piedras y maderas en las calles para impedir el paso de los carros y animales que acarrean el material de las obras, además de no autorizar los propietarios a que se saque arena de sus tierras.
El adelantado Pedro Manrique adquiere en 1435 unas casas situadas entre las iglesias de Santa María y San Martín por un importe de 25.000 maravedís para la construcción del palacio señorial.
Juan II, enfrentado en 1444 con Rodrigo Manrique, le desposee de la villa de Paredes de Nava, expulsando la población por la fuerza a los hermanos de Rodrigo que habían entrado en el alcázar. Cede la localidad a Pedro de Acuña, que vende al concejo todo lo que había sido de Rodrigo, quien pleitea, aunque una carta real de 1445 falla a favor de la villa otorgándole la propiedad, entre otros bienes, del alcázar.
Tras la muerte de Juan II, Rodrigo Manrique recupera el favor real y la localidad. Muere en 1476 y deja a su hijo la villa "con el alcáçar que yo en ella mandé labrar".
En 1521, pasa junto a la localidad una partida comunera que se dirige a Carrión, ordenando Pedro Manrique, hijo del conde, el cierre de las puertas de la muralla y la defensa de la casa fuerte.
La falta de uso y el alejamiento de sus propietarios provocaron su destrucción. En el siglo XVIII, se le describía como "una casa Palacio con su muralla de canto labrado, sus muros de piedra a todos cuatro aires, hállase la muralla y muros muy maltratada y dentro de ellas ninguna habitación por estar arruinado el palacio y no parecer en el más que algunas paredes de tierra arruinadas".
El Conde de Oñate, en el siglo XVIII, vende los restos del palacio a la empresa constructora del Canal de Castilla que lo utiliza como cantera debido a la escasez de piedra de la zona.
Jesús Gutiérrez Pajares, dueño del terreno que ocupó el palacio o alcázar, solicita en 1892 la permuta de este solar, que da a la plaza de San Martín, por otro propiedad del Ayuntamiento.