El nacimiento de la villa de Grau tiene lugar a mediados del siglo XIII, cuando el rey Alfonso X el Sabio otorga la carta puebla que permite la fundación de este núcleo urbano en el itinerario del Camino de Santiago. El elemento más representativo del surgimiento de la ciudad lo constituye la erección de la muralla, que desempeño cometidos tanto defensivos como fiscales con el cobro del portazgo para el acceso de las mercancías.

La muralla de Grado, de medio metro de espesor y siete metros de altura, cumplió su misión defensiva en múltiples ocasiones históricas. En 1308, protegió a los moscones cuando el conde Gonzalo Peláez de Coalla incendió la villa extramuros con la intención de conculcar sus fueros. Durante la Guerra de la Independencia, defendió alternativamente a invasores y nacionales en sucesivas conquistas y reconquistas de la villa, siendo ordenada su demolición en 1812 ante el temor de que volviera a ser ocupada por los franceses.

De aquella primera muralla apaenas quedan más vestigios que este lienzo Este, que se situa sobre una terraza fluvial del rio Cubia. La fachada norte  del Palacio Miranda-Valdecarzana y la pared medianera del Ayuntamiento fueron edificadas sobre la propia muralla.