El alcázar del Obispo parece ser que ocupó el solar donde hoy se encuentra el Palacio Episcopal. Construido probablemente en tiempos del Alfonso VIII, se levantaba sobre la esquina Noroeste de la muralla, con entrada por la antigua plaza del mercado. En su interior se encontraba la cárcel del obispo.

En la mañana del 27 de mayo de 1217 ocurrió el accidente que causó la muerte del joven rey Enrique I diez días más tarde. Parece ser que mientras jugaba al tejo en el patio de la fortaleza se desprendió una teja que le golpeó en la cabeza.

A finales de siglo, aunque antes de 1296, sufrió el incendio de una de sus torres.

En 1446 Juan II remite una carta el corregidor de Palencia en la que menciona que el palacio tenía "puerta falsa en la cerca" por la que el prelado podía hacer entrar y salir a quien él quisiese.

Años después tiene lugar la "Farsa de Avila" por la que la nobleza castellana, enfrentada a Enrique IV, declara rey a su hermano Alfonso. En ayuda del primero acudirá el obispo palentino Gutierre de la Cueva, hermano del favorito del rey, lo que aprovecha Don Sancho de Castilla, representante de la liga nobiliaria en Palencia, para leer en pública asamblea una carta del nuevo monarca por la que ordena a los vecinos derribar el alcázar del obispo.

A pesar de la mediación del cabildo catedralicio para impedirlo, el 12 de julio de 1465 más de quinientos hombres pertrechados con palos, azadones, palancas de hierro y otras herramientas de carpintería derribaron la fortaleza, lo que provocó que la Santa Sede declarase un "entredicho apostólico" por el que durante un año no se celebraron oficios eclesiásticos en la ciudad.

El actual palacio episcopal se levanta en el mismo solar donde se ubicaba el alcázar. Construido a finales del siglo XVIII, desde el siglo anterior los prelados palentinos se alojaron en el palacio de Don Sancho.