Rodeaba la villa una muralla cuyo trazado venía a coincidir con la actual carretera de circunvalación, levantada a principios del siglo XIII, formada por piedra y tierra. En el siglo XIV se amplía por el sur con una segunda cerca en torno al monasterio de Santa Clara, abriendo un postigo en la muralla para comunicar la villa con el nuevo recinto, conocido como la Puebla del monasterio.
Según figura el plano de Coello de 1852, contaba con seis puertas: de Revilla, Santa Eugenia, San Pedro, Santoyo, Santa Clara y San Martín, aunque la de Santoyo o Santa María como también se la menciona, debía estar ya arruinada puesto que Madoz pocos años antes no la menciona, aunque si cita la de Revilla derribada en 1749. No obstante aún se conservaban vestigios de la puerta de Santoyo en 1927.
Las puertas de Santa Eugenia y Santa Clara fueron derribadas en 1914, asi como los restos de la de San Pedro. En esa fecha ya había desaparecido la de Revilla, también denominada de San Marcos o Real. Según Anacleto Orejón la de Santa Clara era la más elegante de todas.
La de San Martín es la única que se conserva. Esta magnífica puerta, construida en el siglo XV, se enmarca dentro de una alta y esbelta torre con un gran arco apuntado en el exterior y rebajado en el interior. Encima de ella tres aspilleras en el frente y una más a cada lado, la servían de defensa. Estaba coronada por almenas con remate piramidal. En su interior se aprecian claramente dos pisos. Debe su nombre a la imagen del santo colocado sobre su arco.
Adosado al convento de Santa Clara se encuentran los restos rehabilitados de un esbelto torreón y de un lienzo de la muralla. El torreón se asemeja en la construcción a la puerta de San Martín, almenas con remate piramidal y aspilleras.
Estos restos probablemente correspondían a la segunda cerca que rodeaba el Barrio de la Puebla, que pertenecía a la jurisdicción del convento de Santa Clara por favor otorgado por el rey Pedro I. A finales del siglo XIV fue derribada de forma injustificada por el señor de Astudillo, Fernán Sánchez de Tovar.
La puerta de Santa Clara se encontraba cerca del torreón y las llaves de la misma las tenía la abadesa del convento. Fue tapiada en varias ocasiones por Fernand Sánchez de Tovar al negarse la abadesa a entregárselas. Se conserva una fotografía de la misma en el Catálogo Monumental de la Provincia de Palencia, en la que se ve una soberbia torre-puerta realizada con buena cantería, probablemente en el siglo XIII, presentando al exterior un alto arco menos apuntado que la de San Martín, con su clave adornada con un escudo, y al interior un arco rebajado.
También existe una fotografía de la puerta de Santa Eugenia, igualmente del XIII, en este caso publicada en la Historia de Astudillo, de Anacleto Orejón. Muy similar a la de San Martín, con arco menos apuntado aunque de gran altura. Entre sus arcos se instaló una pequeña capilla humilladero y se remató la puerta con una modesta espadaña.
Asimismo, la puerta de San Pedro, contó con otra capilla dedicada a Nuestra Señora de las Nieves, abierta al culto en 1714.
Se sabe también de la existencia de otra puerta, situada entre la de Revilla y San Martín, denominada de San Antón o del Castillo, ubicada junto a la fortaleza, ya desaparecida a mediados del siglo XIX.
A partir del último tercio del siglo XVIII la muralla fue desapareciendo al arruinarse y por el uso de su material por parte de los vecinos para empedrar las calles.
En el subsuelo de la población, sin salir del recinto que delimitaba la muralla, existen una serie de pasadizos hipogeos situados debajo de las casas, siguiendo la fachada de las mismas y comunicados entre si. Están revestidos con sillería, con bóvedas de cañón y arcos fajones. Según algunos autores pudieran tratarse de "minas" que permitieran sorprender al enemigo desde la retaguardia. Parte de estos pasadizos se cegaron y otros han servido de bodega.