Im Jahr 1895 entstanden einige neue Vereine, so dass sich ein für die damalige Zeit schon ganz netter Spielbetrieb ermöglichen ließ. Im Herbst des Jahres holte unser Club den ersten Gast aus der Fremde nach Wien, den Grazer Akademisch-Technischen Radfahrerverein. Insgesamt wurden neun Spiele in diesem Jahr ausgetragen, der Erzfeind Cricket am 3. November erneut geschlagen. 5:4 stand es am Ende, nachdem die Blau-Schwarzen zur Pause 1:4 im Vorteil lagen. Doch ein Hattrick Franz Jolis und ein weiteres Goal ermöglichte trotz erbittertster Gegenwehr den zweiten Sieg über Cricket, womit die Begegnungen mit dem zweiten "Erstling" pari standen.
Der neue Sport zog immer weitere Aufmerksamkeit an. Die Presse nahm im Jahre 1896 erstmals Notiz von den Fußballern, das "Neue Wiener Tagblatt" brachte in seiner Abendausgabe nunmehr regelmäßig in der neu geschaffenen Spalte "Rasenspiele" Notizen, die vom ersten Fußballredakteur Felix Schmal gesammelt wurden. Im Frühjahr wurden erstmals Prager Gäste in Wien begrüßt, der Klub hieß Regatta und war sehr spielstark. Die Prager gewannen nach schönem Spiel 1:0. Kurz nach diesem Gastspiel kam es zur ersten Reise der Vienna. Das Ziel war Graz, wo die Retourbegegnung mit den "Akademikern" stattfand. Das Spiel endete 1:1 unentschieden.
Mit Ende der Frühjahrsaison 1896 musste von der Kuglerwiese Abschied genommen werden. Man übersiedelte auf die Kreindlwiese, die bereits um vieles größer war und gegen die Straße zu eingeplankt war, allerdings hing der Platz beträchtlich, so dass eine der beiden Mannschaften immer bergauf spielen musste. Im November 1896 gastierte unser Klub erstmals in Prag, es handelte sich um die Retourbegegnung mit der Prager Regatta.
Im darauf folgenden Jahr gab es bereits so viele Sportbegeisterte in den Reihen des Klubs, dass eine zweite Mannschaft gebildet werden konnte. Der Betrieb vergrößerte sich zusehends, im April wurde anlässlich des Fußballderbys Vienna - Cricket erstmalig ein Eintrittspreis von zwanzig Kreuzer eingehoben, um - wie es wörtlich hieß - "den Andrang zu schwächen". Erstmalig wurden auch die Reserven gegeneinander eingesetzt.
Dem Vienna-Spieler Lambacher wurde durch einen allzu starken Rempler des Cricketers-Spielers Flavin - einem Iren - das Schlüsselbein gebrochen, was zum ersten Spielabbruch der Wiener Fußballgeschichte führte. Flavin wurde von der Polizei angezeigt und vor Gericht gestellt - jedoch endete die Angelegenheit mit einem Freispruch, womit eine prinzipielle Entscheidung betreffend Verletzungen während des Spiels getroffen war.
Im Herbst 1897 tauchte ein neuer Name in den Reihen unseres Klubs auf, M.D. Nicholson, ein Engländer, der den Wienern bisher ungeahntes Können präsentierte und vor allem auf dem Gebiet des Trainings gänzlich neue Methoden einführte. Nicholson war ein ehemaliger Profispieler, der als Angestellter des Reisebüros Cook nach Wien gekommen war. Seine Tätigkeit läutete eine Glanzperiode der Vienna ein, aber auch der gesamte österreichische Fußballsport hat ihm - insbesondere in organisatorischer Hinsicht - sehr viel zu verdanken. Nicholson ist als Gründer des Fußball-Verbandes anzusehen. Er regte durch seinen Verein die Gründung eines "Komitees zur Veranstaltung von Fußballwettspielen" an. Dieses Komitee war der Vorläufer der späteren Fußball-Union, die sich dann im Jahre 1904 in den Österreichischen Fußball-Verband umwandelte, den heutigen ÖFB.
Seinen ersten Auftritt auf dem Rasen hatte Nicholson beim neugegründeten Challenge-Cup, der ersten Konkurrenz, die in Österreich im Fußball zur Austragung gelangte. Vienna verlor das erste Cupspiel gegen die Cricketer 2:3, aber darauf gab es bis zur Beendigung der Saison 1897/98 keine einzige Niederlage mehr. Nicholson hatte aus der Vienna eine sehr starke Mannschaft geschaffen.
