Az egyesület fennállásának legnagyobb nemzetközi sikerét a 2000-2001-es szezonban érte el, amikor a Bajnokok Ligájában túljutott az első csoportkörön, és ott volt a legjobb 16 között. Abból a csapatból mára azonban szinte senki sem maradt, csak Günther Neukirchner, Korsós György, Gerold Strafner és Mario Haas játszik azóta is Grazban (bár utóbbi azóta megjárta a francia RC Strasbourg együttesét is). A sikeredző, Ivica Oszim egészen a legutóbbi idényig maradt, ám a bajnokság közben a sikertelenség hatására menesztették, és utódja a csapat egykori futballistája, Franco Foda lett, aki akkor már pályaedzőként tevékenykedett a gárdánál. Ő sem tudott azonban javítani a csapat helyzetén, így a Sturm csupán hetedik lett az előző szezonban.
Márpedig Kartnig számára ez kevés volt, éppen ezért az elnök úgy döntött, hogy kicseréli a játékoskeretet, és a szakmai stábon is változtat. Foda szerződését nem hosszabbította meg, így a kispadra a francia Gilbert Gress érkezett. A 61 esztendős szakember meglehetősen nagy tapasztalattal rendelkezik az európai labdarúgásban: edzői pályafutása során dolgozott az RC Strasbourgnál, az FC Bruges-nél, a Neuchatel Xamaxnál, a Servette FC-nél, az FC Zürichnél és az FC Metznél, de volt a svájci válogatott szövetségi kapitánya is. Érdekesség, hogy Gresst Oszim ajánlotta be a Grazban, hiszen egykoron együtt futballoztak a Strasbourgban, ráadásul Gress legutóbb Japánban dolgozott - ott, ahol Oszim új állást talált magának.
Nemcsak a kispadon történt változás a klub háza táján, hanem a játékoskeret is jelentősen kicserélődött. Noha Kartnig korábban váltig hangoztatta, hogy elsősorban a saját nevelésű fiatalokra akar építeni, ehhez képest csupa rutinos labdarúgó érkezett, ráadásul többségében idegenlégiósok. Az egyetlen kivételt a városi riválistól leigazolt csatár, Roland Brunmayr jelentette, a többi új szerzemény viszont egytől egyig külföldi volt, és nem is a fiatalabb évjáratból. Szintén a GAK-tól jött a szerb középpályás, Boban Dimitrovic, a bajnokcsapat FK Austria Wientől a cseh középpályást, Martin Haseket sikerült elcsábítani, a belga RSC Anderlechttől a veterán portás, Filip de Wilde írt alá a Sturmhoz, a sort pedig a francia hátvéd, Franck Silvestre zárta.
A csapat tehát szinte teljesen kicserélődött, ám az eredmények ennek ellenére sem jöttek, sőt: az első öt fordulóban a grazi együttes nyeretlen maradt, és bár a hatodik játéknapon végre sikerült megszerezni az első győzelmet, az újabb vereség nyomán Kartnig úgy döntött, hogy kirúgja Gresst. "Ezzel a csapattal nem az utolsó előtti helyen kellene állnunk" - jelentette ki az elnök, aki a szlovén Mihajlo Petrovicot ültette le a kispadra, aki egykoron a Sturm focistája volt. Ő legutóbb a Mura Murska Sobotát irányította, de korábban dolgozott az Olimpija Ljubljanánál és a BST Domzalénál is. A hírek szerint Petrovic olyan szerződést írt alá, hogy fizetését az eredményekkel arányosan kapja, és talán ennek is köszönhetően a csapat szereplése javult valamicskét: a Sturm immár a hetedik helyen áll a bajnokságban.