In der Saison 1959/60 übernahm Josef "Joschi" Walter die Leitung der Austria und führte erstmals das Leistungsprinzip ein – am Schreibtisch wie am Rasen. Er erkannte den Fußball als Geschäft und orientierte sich entsprechend an den Rahmenbedingungen. Walter sollte helfen, die ständig wachsenden finanziellen Probleme der Austria abzubauen.
Der Kader wurde verkleinert, jungen Talenten das Vertrauen ausgesprochen. Ein deutlicher Leistungsanstieg war die Folge, in der Meisterschaft ging es aufwärts. Am 5. September staunten die Zuschauerinnen und Zuschauer nicht schlecht, als die jungen Violetten mit den unbekannten Spielern Peter Popek, Horst Hirnschrodt, Ernst Fiala, Adolf Blutsch und Peter Vargo Rapid in Hütteldorf mit 2:1 schlug. Es war gleichzeitig der erste Derbysieg seit fünf Jahren.
1960/61 konnte die Mannschaft unter Trainer Karl Schlechta erstmals nach zehn Jahren wieder Meister werden. Mit einer Mannschaft, die neben guter Technik vor allem durch Kampfkraft überzeugte. In den kommenden Jahren – auch 1962 und 1963 konnte der Meistertitel eingefahren werden – wurde vermehrt die Tendenz zum Kauf von Legionären spürbar.
Der Grund war darin zu sehen, dass die Preise für inländische Nachwuchskräfte wesentlich gestiegen waren und man dem Publikum mit ausländischen Spielern neue Attraktionen bieten wollte. Der Kauf des Brasilianers Waldemar Graziano, allgemein bekannt unter seinem Künstlernamen Jacare, war der violette Beitrag zu diesem Trend. Er war der erste dunkelhäutige Fußballer Österreichs und bestach durch seine blendende Technik.
In der Saison 1963/64 errang die Austria den zweiten Meisterschaftsrang und das Cupfinale. So gut wie jeder andere Klub wäre mit dieser Bilanz mehr als zufrieden gewesen, nicht so die Austria. Die Neuerwerbungen des Vorjahres mussten den Klub wieder verlassen. Dafür wurde vom Sportclub Routinier Erich Hof verpflichtet, Torhüter Özcan "Ötschi" Arkoc sollte der Verteidigung mehr Sicherheit geben. Ansonsten wurde aber nach jungen Talenten Ausschau gehalten: Robert Sara, Thomas Parits, Karl Kodat, Alfons Dirnberger und der legendäre Johann "Buffy" Ettmayer kamen in die Mannschaft. Mit Sara hatte man eines der künftigen Austria-Idole verpflichtet: 21 Jahre lang spielte er für die Violetten, absolvierte dabei 727 Pflichtspiele und sammelte neun Meistertitel sowie sechs Cupsiege.
Mit diesem Team wurde bei der Austria eine harte Welle eingeleitet: Abbau der leistungsschwächeren Auslandsstars, profiähnliches Training, modernes Fußballspiel. Die Austria, allen voran Joschi Walter, erkannte als erster die Zeichen der Zeit und so war der Klub der erste Verein in Europa, der mit der Schwechater Brauerei einen Sponsor fand und auf den Dressen von nun an groß das Logo des Partners trug. Die Medien und auch viele Fans protestierten dagegen und sahen bereits das Ende des Fußballs gekommen.
Die sportlichen Erfolge waren zufriedenstellend, doch die Führung der Austria wollte mehr. Das Duo Walter/Stroh hatte vorerst ohne große Öffentlichkeit an dem Plan gearbeitet, durch eine Fusion der Austria mit Admira Energie einen Großklub zu schaffen, der im europäischen Fußball oben mitmischen sollte – die Verhandlungen scheiterten jedoch. Walter und Stroh zogen die Konsequenzen und demissionierten, Ocwirk schloss sich ihnen kurze Zeit später an.
Zu dieser Zeit wurde auch ein weiteres blutjunges Talent engagiert, das schon damals seine Anlage zum Weltstar durchblicken ließ: Felix Gasselich. Später hatten auch Herbert Prohaska, Erich Obermayer, Ernst Baumeister und Hans Pirkner ihren Durchbruch bei den Veilchen.
Am 26. August 1973 fand das erste Spiel im neuen Franz-Horr-Stadion, der heutigen Generali-Arena statt. Die Austria setzte sich gegen die Vienna klar mit 4:1 durch und feierte ihre neue Heimat.
"Die Zeiten haben sich geändert. Ein Fußballverein ist heute längst kein Hobby mehr, das man so schlecht und recht durch die finanziellen Wirrnisse steuert, ganz besonders gilt dies bei den Spitzenklubs. Sie sind in unseren Tagen Unternehmen, die neben dem sportlichen Ziel auch die wirtschaftlichen Gesetzmäßigkeiten beachten müssen", erkannte Joschi Walter, der zur Austria zurückkehrte, bereits in den siebziger Jahren.
Ab 1977 haben die Austria Tabakwerke die Sponsor-Tätigkeit übernommen und die Austria konnte einen ihrer größten Erfolge unter dem neuen Namen Austria-Memphis erringen. Im Spieljahr 1977/78 wurde man überlegener Meister und brach alle bisher bestehenden Rekorde: Noch nie zuvor hatte ein Klub so viele Punkte errungen und noch nie mit einem so großen Punkteabstand die Meisterschaft gewonnen. Dazu stieß erstmals ein österreichischer Klub in das Finale eines Europacups vor. Dieses Erfolgsjahr stand im Zeichen eines Fußballers, des Fußballers des Jahres 1978: Herbert Prohaska!
Die große Mannschaft des Jahres 1978 blieb nahezu unverändert, dementsprechend war die Austria in Österreich eine Klasse für sich. Vier Meisterschaften holte man en suite und international hatten die Violetten Erfolge, die von anderen österreichischen Clubs bis heute nicht erreicht wurden.
1978 gelang sensationell der Einzug in das Finale des Europapokals der Pokalsieger. Auf dem Weg dorthin eliminierten die Violetten Cardiff City, Lokomotiva Kosice, Hajduk Split und Dynamo Moskau. Vor allem Torhüter Hubert Baumgartner brachte die gegnerischen Teams mit seinen Paraden und gehaltenen Strafstößen regelrecht zur Verzweiflung. Im großen Finale in Paris geriet die Austria gegen das starke Team des RSC Anderlecht früh in Rückstand und unterlag durch weitere Kontergegentore mit 0:4.
Ein Jahr später erreichte man als bisher einziger heimischer Verein das Semifinale des Meistercups, der heutigen Champions League. In den Jahren darauf eliminierte man reihenweise Gegner der europäischen Elite, Namen wie Inter Mailand und FC Barcelona wurden aus dem Bewerb geworfen. 1983 zogen die Veilchen erneut in das Semifinale des Cupsieger-Bewerbs ein.
Die größten Stars der 1980er Jahre waren Herbert Prohaska, der ungarische Teamkapitän Tibor Nylasi und Toni Polster. Mit ihnen sicherten sich die Veilchen 1984, 1985 und 1986 drei Meistertitel in Serie, zuletzt sogar das Double. In den nächsten Jahren war man zwar national immer an der Spitze zu finden, international blieben die Erfolge aber aus.