Im letzten Jahrzehnt des 12. Jahrhunderts wurde mit der Errichtung der Stadtmauer begonnen, ursprünglich etwa 8 m, mit Fundament etwa 10 m hoch, mit einer Mauer teilweise in Opus-spicatum-Technik. Im ersten Viertel des 13. Jahrhunderts wurden die vier Ecktürme, zehn Zwischentürme und vier Stadttore erbaut. Die Außenbefestigung der Vorstädte erfolgte mit Erdwällen, Palisadenzäunen und Mauern, jeweils den vier Toren zugeordnet. Der umlaufende Stadtgraben wurde von der Fischa, vom Kehrbach und mit Grundwasser geflutet.
In der Mitte des 15. Jahrhunderts wurde die Stadtmauer mit einem zinnenbekrönten Wehrgang und sechs Zwischentürmen mit Quadermauerwerk und bossierten Ecken ausgebaut.
Im 16. und 17. Jahrhundert erfolgte eine Verstärkung der Stadtbefestigung durch den Neubau von weiteren Türmen (der äußere Turm des Fischauer-Tores signiert 1613, der äußere Turm des Ungartores datiert 1614) und durch den Bau von Bastionen. (Als im 19. Jahrhundert die Tore abgebrochen wurden, wurden deren Wappensteine sichtbar in die Fassade des Rathauses vermauert.) Außerdem wurden von 1551 bis 1557 durch den Baumeister Johann Tscherte bei der Südwestecke der Südmauer Gewölbekeller als Kasematten für die Einlagerung von Waffen ausgebaut.
Ab 1783 wurden die Wassergräben zugeschüttet und die Außenbefestigungen abgetragen. Nach dem Stadtbrand 1834 wurden die Stadttore wieder instand gesetzt. 1837 erhielt die Westmauer bei den Kasematten – im Verlauf der heutigen Bahngasse – das fünfte Stadttor, das sogenannte Ferdinandstor. 1846 wurde die Kapuzinerbastei bzw. Grübelschanze demoliert. Im dritten Viertel des 19. Jahrhunderts wurden die Stadttore geschleift, 1851/1862 das Neunkirchner-Tor, 1861 das Fischauer-Tor, 1864 das Wiener-Tor und Ungartor, 1873 das Ferdinandstor. 1954 erfolgte die Abtragung des Mühlturmes/Basteiturmes, bedingt durch die Anlegung der Grazer Straße. 1979 wurde der Deutschherrenturm abgetragen, um Raum für den Ausbau des Allgemeinen Öffentlichen Krankenhauses zu schaffen, ein ca. 1 m hoher Mauerrest ist im Hof der Physikalischen Abteilung erhalten.
1995/1997 erfolgten archäologische Untersuchungen im Bereich des Neunkirchner-Tores, 1997 Grabungen im Bereich des ehemaligen Fischauer-Tores in der Herzog-Leopold-Straße. 2016/2017 fanden weitere Grabungen im Zuge der baulichen Vorbereitungen auf die Niederösterreichische Landesausstellung 2019 statt.
Bauten
Auf allen vier Seiten sind großteils sichtbare Reste der Stadtmauer erhalten.
Erwin Reidinger: Wiener Neustadt 1192 – Grundwasser und Stadtplanung. In: Unsere Heimat. Zeitschrift für Landeskunde von Niederösterreich, 2/2000, 139–149.