El recinto amurallado medieval de la ciudad fue construido en un momento indeterminado del siglo XII, (ver discusión y notas 1 y 2) unos años antes de que el rey Sancho VI de Navarra^[4]​ fundara la villa en 1181 bajo el nombre de Nueva Victoria.^[5]​ Este recinto murado ya consta en el fuero concedido el mismo año de la fundación.^[6]​

Durante los últimos siglos permaneció oculta entre las edificaciones del casco histórico, hasta que un equipo de investigación arqueológica de la Universidad del País Vasco llevó a cabo unas excavaciones arqueológicas en el subsuelo de la catedral de Santa María en 2001, en las que fueron descubiertos los restos de las zapatas de la antigua muralla.^[7]​

Después de analizarse los restos se pudo comprobar que la citada zapata correspondía con la primera muralla que rodeaba el poblado pero que tenía una antigüedad anterior a la fundación de la ciudad. Ello denotaría un cierto poder económico y de liderazgo social, desconociéndose hasta el día de hoy quienes pudieron ser sus impulsores o de que se defendían empleando para ello tantos recursos.

Aunque el recinto amurallado tenía una longitud total de unos 900 metros y contaba con unos 22 torreones, actualmente solo se conserva cerca de la mitad. En 1968 bajo la dirección de Emilio y Luis Ángel Apraiz se restauró con criterios historicistas en estilo lombardo el tramo junto al palacio de Escoriaza - Esquivel, esta intervención es considerable como falso histórico. Tras el descubrimiento realizado en las excavaciones de la catedral se decidió llevar a cabo una restauración de los restos de la muralla que se conservaban en la ladera oeste.

• Primera fase: vio la luz en 2006 y puso al descubierto el tramo que corresponde a las traseras de los números 98 al 104 de la calle Correría. Quedaron a la luz unos 136 metros de muralla y los antiguos restos del matadero y del mercado del siglo XIX.
• Segunda fase: vio la luz en 2010 y ofrece la posibilidad de contemplar 160 metros de muralla en las traseras de San Miguel a través de una celosía de madera que imita la forma de la muralla que no se conserva.
• Tercera fase: se ubica entre las dos primeras fases y aun está por acondicionar.

A través de la Fundación Catedral de Santa María se pueden concertar visitas guiadas^[8]​ que llevan a los turistas a través de las dos zonas ya recuperadas. En ellas se pueden observar desde las desacertadas restauraciones llevadas a cabo al estilo de la época en los años 1960, pasando por los distintos tipos constructivos, a la más moderna celosía de madera de cedro que recrea las dimensiones de la muralla en su máximo esplendor.

•   Wikimedia Commons alberga una categoría multimedia sobre Muralla de Vitoria.