Sturm perustettiin vuonna 1909 työväen seuraksi vastavoimaksi toiselle grazilaisjoukkueelle GAK:lle. Suurempaa menestystä joukkue saavutti ensi kerran vasta 1980-luvulla Otto Baricin valmennuksessa. Kaudella 1982–1983 Sturm sijoittui liigassa kakkoseksi ja pääsi eurokentille. Joukkue raivasi tiensä UEFA Cupissa aina puolivälieriin saakka, missä se putosi Nottingham Forestille vasta jatkoajan jälkeen.
Sturmin suurinta menestyskautta oli 1990-luku, jolloin joukkue oli vahva tekijä Euroopan kentillä. 1992 uudeksi puheenjohtajaksi tuli Hannes Karting ja valmentajaksi Heinz Schilcher. Aiemmin Sturm oli toiminut pienellä budjetilla ja kärsinyt talousvaikeuksista, mutta uusi voimakaksikko toi joukkueeseen useita kovan luokan pelaajia ja kehittivät omaa junioritoimintaa. Joukkue raivasi tiensä uuteen Zehnerligaan (1. Bundesliiga). 1993 valmentajaksi tuli Milan Djuricić ja seura pysyi pääsarjassa.
1994 valmentajaksi tuli bosniahertsegovinalainen Ivica Osim. Sturmin pelaajisto koostui pääasiassa omista kasvateista. Kauden päätteeksi Sturm sijoittui liigassa kakkoseksi. Vuotta myöhemmin se voitti ensimmäistä kertaa historiansa aikana Itävallan cupin ja oli toistamiseen liigassa toinen. Ensimmäisen liigamestaruutensa Sturm voitti vuonna 1998. Mestaruus tuli todella ylivoimaiseen tapaan ja varmistui jo seitsemän kierrosta ennen kauden päätöstä. Ero kakkoseksi sijoittuneeseen Austria Wieniin oli 19 pistettä Tuolloin joukkueen rungon muodosti kolmikko Mario Haas, Hannes Reinmayr ja Ivica Vastić. Seuraavalla kaudella Sturm uusi mestaruutensa ja voitti lisäksi cupin sekä liigacupin.
Kaudella 1999–2000 Sturm pääsi myös ensimmäistä kertaa Mestarien liigan lohkovaiheeseen pudottuaan vuotta aikaisemmin karsinnoissa. Alkulohkossa sijoitus oli kolmas ja Sturm pääsi jatkamaan UEFA Cupissa, missä se kuitenkin putosi saman tien Parmalle. Bundesliigassa sijoitus oli neljäs. Seuraavaksi kaudeksi Sturmin joukkue oli heikentynyt huomattavasti monien avainpelaajien lähdettyä, mutta silti se kykeni sijoittumaan liigassa kakkoseksi. Valmentaja Osim sai lähteä.
Eurocup-menestyksestä saatuja rahoja ei suunnattu junioritoiminnan kehittämiseen. Sittemmin seura on vajonnut Itävallan Bundesliigan keskikastiin ja kärsinyt huomattavista taloudellisista vaikeuksista. Vuonna 2008 seura oli yksi kolmesta Intertoto Cupin voittajasta selviydyttyään UEFA Cupin toiselle karsintakierrokselle, missä se putosi sveitsiläiselle FC Zürichille.
Saavutuksia
Itävallan mestaruus (4): 1998, 1999, 2011, 2024
Itävallan cupin voitto (7): 1996, 1997, 1999, 2010, 2018, 2023, 2024
