Im Sommer 1994 gelingen Schilcher und Kartnig ein weiteres Wunder. Sie lotsen den letzten gesamtjugoslawischen Teamchef – auch aufgrund des Krieges im ehemaligen Nachbarstaat – nach Graz. Zudem verpflichten sie den kroatischen Kreativspieler Ivica Vastić. Mit weiteren Talenten wie Mario Haas, Arnold Wetl, Markus Schopp, Gilbert Prilasnig oder Günther Neukirchner führt Osim eine neue Spielkultur in der Gruabn ein: Statt Kampf ist Kurzpassspiel die neue Formel, die Schwarz-Weiß langsam aber sicher an die Spitze des österreichischen Fußballs bringt. Bereits in der ersten Saison, 1994/95, wird Sturm unter Osim punktegleich mit Meister Austria Salzburg Vize-, geschlagen nur aufgrund des schlechteren Torverhältnisses. Schon eine Saison später folgt der erste nationale Titel im Profifußball: Zunächst zieht man in der Meisterschaft im entscheidenden direkten Duell der letzten Runde gegen Rapid den Kürzeren, doch nach einem 3:1 gegen die Admira kürt sich der SK Sturm zum Pokalsieger. 1996/97 gelingt die Bestätigung des Cupsieges mit dem neuerlichen Gewinn gegen die Vienna (2:1). Zum Saisonende verabschiedet sich die Anhängerschaft am 31. Mai 1997 nach über 78 Jahren von der Gruabn (3:0 gegen Rapid). Künftig spielen nur noch die Amateure am Sturmplatz.

Der Meisterteller ist endlich in Graz

Es folgt der Umzug ins neu erbaute Arnold-Schwarzenegger-Stadion, der heutigen Merkur Arena, wo das erste Spiel der Saison 1997/98, das Grazer Derby, mit 4:0 gewonnen wird – es sollte der Auftakt für eine fulminante Saison sein. Sturm wird, dank der Tore des magischen Dreiecks Haas – Vastić – Reinmayr, zum ersten Mal in der Vereinsgeschichte Meister – mit dem damaligen Rekordvorsprung von 19 Punkten auf Vizemeister Rapid, fixiert den Titel bereits sieben Runden vor Schluss. Es folgt das Double in der Saison 1998/99 in einem dramatischen Saisonfinish, in dem Sturm binnen weniger Tage zunächst den LASK im Elfmeterschießen im Cupfinale (1:1nV, 4:2iE) bezwingt, das (Jahrhundert-)Derby in der vorletzten Runde in der Nachspielzeit dank eines Tores von Jan-Pieter Martens gewinnt (2:1) und zum Haas-Abschied nach Strasbourg – für die damalige Rekordsummer von über 50 Millionen Schilling – noch gegen den FC Tirol (3:0) den Meistertitel fixiert.

STÜRMISCH IN DER CHAMPIONS LEAGUE

Übertrumpft werden diese Erfolge nur noch durch die dreimalige Serienteilnahme an der Champions League-Gruppenphase von 1998/99 bis 2000/01. Während man unter anderem gegen Real Madrid, Inter, Olympique de Marseille oder Manchester United in den ersten beiden Saisonen in der europäischen Königsklasse noch Leergeld bezahlt, erreicht Sturm im dritten Teilnahmejahr den sensationellen Gruppensieg – vor UEFA-Cupsieger Galatasaray und den nationalen Meistern Rangers FC und AS Monaco. Schwarz-Weiß steht unter den besten 16 Mannschaften Europas und hat in der Zwischenrunde bis zum abschließenden Spieltag noch die Chance auf das Viertelfinale.