Rodeaba a la localidad una cerca almenada de la que hoy no quedan restos, aunque su perímetro es reconocible al estar marcado por la actual circunvalación. Estaba construida de tapial, con refuerzos de piedra en los puntos más importantes y, al menos, una veintena de torres.

Es probable que ya existiese la cerca en 1234 cuando Alvar Pérez de Castro se refugia en la villa y la fortifica debido a su enfrentamiento con Fernando III, quien tras el abandono de la localidad por parte del noble, manda demoler las defensas. En 1296 ya estaba reconstruida y permite resistir el cerco al que fue sometida por parte de la regente María de Molina.

Según indica José Luis Sáinz Guerra, basándose en la existencia de varias calles de trazado curvo alrededor de la iglesia de Santa Eulalia, pudo existir una primitiva cerca alrededor del templo. La llegada de nuevos pobladores favorecidos por los fueros otorgados a la villa hace que se incremente considerablemente la población, en parte procedente de pequeñas aldeas cercanas que se despueblan, obligando a construir una nueva muralla en el siglo XIII.

Contaba con seis puertas de acceso construidas con arcos de piedra de sillar conocidas con los nombres de Puerta de San Juan o de la Villa, Antenoria o Fuentinoria, Ardagón o Salida de Carretas, de Gallegos, de la Fuente o Arco de San Martín y la de Renedo. Salvo la de Antenoria, que daba salida a la antigua ciudad vaccea, las demás comunicaban con los caminos que conducían a Palencia, Villoldo, Villalumbroso, Frechilla y el despoblado de Sahagún el Real, respectivamente.

La Puerta de Antenoria fue la última en desaparecer en 1860 y en ella estaban grabadas las armas reales. Sus piedras se emplearon para la construcción de la fuente de la actual Plaza Calvo Sotelo.

También se tiene noticia de la existencia en 1386 de un par de portillos situados entre la puerta de Gallegos y la de la Fuente.

Cada una de las puertas tenía una persona encargada de su cierre a la caída de la noche y apertura al amanecer, por cuyo trabajo recibía una gratificación anual del concejo, que en 1414 ascendía a 30 maravedís.

Internamente, la villa se organizaba en ocho barrios: Mediano, de la Fuente, Renedo, San Miguel, Calleluenga, San Juan, Ardegón y Gallegos. Calleluenga estaba formado por una sola calle que recorría la muralla por el interior. También existió una importante comunidad judía, que al igual que los barrios, tenía asignada para su mantenimiento y reparación una parte de la misma, incluso se recaudaba una Renta de los Testamentos que abonaban los vecinos al hacer testamento, que se empleaba en la conservación de la cerca.

La conservación de la muralla en perfecto estado exigía labores de mantenimiento y reparación constante. Así por ejemplo, en 1425 se gastan en la misma 53.158 maravedís, además de otros 17.303 en obras puntuales, entre ellas en la puerta de Ardagón y puerta y sobrepuerta de Antenoria. Al año siguiente, se emplean 12.418 en arreglos de la cerca, 16.784,5 en las puertas y sobrepuertas, especialmente en la de Gallegos, y 2.000 más en los cimientos y tapias de la puerta de Ardagón.