La capital palentina se encontraba rodeada por una cerca desde el siglo XI. Construida inicialmente de tierra, se fue modificando debido a restauraciones y a la ampliación de la misma hasta formar "una muralla de piedra de once metros de altura y dos de grueso" como la describe Ricardo Becerro de Bengoa en 1874. Hoy desgraciadamente tan sólo es un recuerdo.

En un primer momento el muro Norte iría desde el Alcázar del Obispo, Actual Palacio Episcopal, a la Puerta de Monzón, hoy Plaza de León, con la Puerta del Arco en el centro. Seguía después por el Este hasta la Puerta de Burgos, actual Plaza de Isabel la Católica, para llegar hasta el río bordeando la iglesia de San Miguel por el Sur. Por último, al Oeste bordeaba el río hasta unirse de nuevo con el Alcázar. En este último lienzo se abrían las puertas correspondientes a las Puentecillas y la que posteriormente sería del Puente Mayor.

Del otro lado del río también debió existir una cerca que en el siglo XVII, según Quadrado, aún se la veía "sobrevivir a los barrios que circundaba allende el río, donde se abría la puerta de San Julián".

De acuerdo con el fuero de 1180, tanto el Obispo como el cabildo podían nombrar una serie personas exentas del pago de tributos y de colaboración en tareas comunes, su elevado número provoca las protestas del vecindario con motivo de la reparación de la muralla a finales del siglo XII, teniendo que mediar el rey en 1191 para llegar a un acuerdo para que los excusados participen en las tareas de conservación y reparación de muros y fosos durante diez años.

A finales del siglo XIII la ciudad se amplía con la creación del Barrio Nuevo, lo que provoca que se desplace la muralla al Este hasta la actual Calle Mayor. Estaría construida con canto. Queda fuera de ella el barrio de La Puebla, fundado en 1165 en terrenos cedidos por el cabildo.

Tras la llegada de varias órdenes religiosas que edifican conventos e iglesias extramuros de la ciudad se hace necesario ampliar el perímetro de la cerca en la primera mitad del siglo XV. Su nuevo trazado fue ya definitivo, manteniéndose hasta el siglo XIX en que se destruyen las murallas.

Su contorno lo marcaban por el Norte las actuales avenidas de Simón Nieto y Antigua Florida, al Este las de Casado del Alisal y Manuel Rivera, al Sur el Paseo del Salón y la Plaza Pío XII, y al Oeste iba paralela al río.

Las puertas existentes a mediados del siglo XV eran las de Monzón, Pan y Agua, Puente, San Lázaro, Barrio Medina, Santa Marina, Valdesería, Puentecillas, y Mediana. Las tres primeras eran las principales y contaban con torre o torres para su defensa al igual que la de San Lázaro. También estaban los postigos de la Pellejería y de la Corredera.

En 1497 parte de la muralla se hallaba caída y su reconstrucción era uno de los principales problemas de la ciudad junto con el estancamiento de las aguas del Carrión en verano y el asentamiento de la carnicería. Ese año se manda al Concejo que empiedre la calle Mayor que atraviesa la ciudad desde la Puerta de Monzón a la del Mercado.

La restauración de la cerca fue una constante en los siguientes años. En 1509 se gastan 50.000 maravedís en reparar tres trozos de la cerca y otros 56.000 en la reparación del puente Mayor y su torre. Entre 1511 y 1512 el gasto fue de 38.000 maravedís en los que se incluía la confección de una "pontezilla en el mercado". Dos años más tarde se reconstruye otro pedazo de cerca, almenas y un cubo valorados en 60.000 maravedís y se realiza "una pontezilla a la puerta de Barrio Medina", con un coste de 10.000 mrs.

Debido a la epidemia que asoló Palencia a principios de 1597 se cierran las puertas de la ciudad manteniéndose abiertas únicamente las tres principales: Monzón, Mercado y Puente.

A principios del siglo XVIII siete eran las puertas de acceso a la ciudad. Además de las tres principales de Monzón, Mercado y Puente Mayor, donde se recaudaban los arbitrios, estaban las de San Lázaro, San Juan, el Portillo del Río y Puentecillas, además de los portillos del Carmen y del Matadero. Por la noche se cerraban a las nueve en invierno y a las once en verano, aunque en ocasiones se mantenían abiertas una hora más.

Durante la Guerra de la Independencia, las tropas francesas ocuparon temporalmente la ciudad. Tras su marcha se derribó parte de la muralla paralela al río, entre el Puentecillas y el puente Mayor, para evitar que se hicieran fuertes por segunda vez en ella.

En de abril de 1823, en previsión de un ataque inmediato del Cura Merino, se reparan y fortifican las partes más deterioradas de la cerca y se abre un gran foso para proteger la zona que carecía de ella. También se tapian la puerta de San Juan, el portillo del Río y los postigos del Carmen y del Matadero.

Quince años después la amenaza son las facciones carlistas por lo que se derriba la ermita del Pradillo y con sus piedras se reconstruye la zona desprotegida de la muralla que bordea el río.

También se vuela el ojo del Puentecillas más cercano a la ciudad que permanece reconstruido en madera hasta finales del siglo XIX.

En 1858 se comienza la construcción de un nuevo consistorio, aprobándose el uso de piedras procedentes del rebaje de la muralla. El año anterior se había aceptado su rebaje por la zona del Salón.

Con la pérdida del valor defensivo ante el desarrollo de nuevos tipos de armas y los frecuentas problemas de salud pública que ocasionaba, en 1868 se sustituye la muralla por una cerca de carácter fiscal. Ese mismo año se derriban las emblemáticas puertas de Monzón, la zona de la Corredera en 1881, la puerta del Mercado en 1909, al año siguiente los lienzos de la ronda de San Lázaro y en 1917 los de la ronda del Estudio.