העיר הוקמה בשנת 1194 על ידי לאופולד החמישי, דוכס אוסטריה, שמימן את בנייתה מן הכופר ששולם לו מאנגליה על מנת לשחרר את מלכם ריצ'רד לב הארי, שהוחזק על ידו כבן ערובה בעיירה האוסטרית דורנשטיין. השם "וינר נוישטאדט" שימש לראשונה כשם מבצר שנבנה בעיר על מנת להגן מפני הונגריה הסמוכה. העיר קיבלה זכויות מיוחדות במטרה לאפשר לה לשגשג.
בזמן מלחמת העולם השנייה הייתה וינר נוישטאדט מרכז תעשייתי, פעלה בה שלוחה של מפעל "Rax-Werke" אשר ייצרה מכונות וטיליV-2 ובה הועסקו כ-1,000 עובדי כפייה ממחנה הריכוזמאוטהאוזן.[1][2] בעקבות היותה מרכז תעשייתי, הופצצה העיר קשות, בין היתר במבצע פוינטבלאנק (או: הנחיית פוינטבלאנק) (אנ'), מתוך 4,000 מבנים שעמדו בעיר, נותרו בשלמותם רק 18[3] והיא איבדה רבים מתושביה.
תחבורה
וינר נוישטאדט היא אחד הצמתים התחבורתיים החשובים באוסטריה. בעיר ישנם שני נמלי תעופה, אחד צבאי, שהוא נמל התעופה הראשון שהוקם באוסטריה, ואחד אזרחי. העיר מחוברת גם למסילת רכבת ולכביש מהיר. בעיר ישנה גם תעלה, "וינר נוישטאדטר קאנאל", שהייתה אמורה להגיע עד טריאסטה, אולם בנייתה מעולם לא הושלמה.