Anfänge

Nach der Auflösung der Band Circle of Grief waren Schlagzeuger Sebastian Albrecht und Bassist Peter Cerveny auf der Suche nach weiteren Musikern für ein neues Projekt. Mit den Gitarristen Armin Haas und Michael Liewald sowie Keyboarder Matthias Müller begann man mit dem Songwriting. 2009 fand man mit Alexander Schirmer einen passenden Sänger und begann nach der Neugründung die Vorbereitung für ein erstes Album. Dieses wurde Anfang 2011 unter dem Titel A Coming Storm veröffentlicht und erntete in der Fachpresse meist gute bis sehr gute Kritiken. Erste Auftritte fanden in diversen Clubs im fränkischen Raum statt, größere Bekanntheit erlangte man unter anderem als Support von Bands wie Rage, Saltatio Mortis oder DragonForce sowie auf diversen überregionalen Festivals. Der steigende Bekanntheitsgrad in der Szene bescherte der Band den Mittelalter-Rock-Award auf dem Festival-Mediaval 2011.

Zweites Studioalbum

Ende 2011 begannen die Aufnahmen für das zweite Studioalbum. Diese fanden in den bandeigenen Mind-EQ-Studios in Bayreuth statt, für die man auch Orden-Ogan-Sänger Sebastian „Seeb“ Levermann gewinnen konnte, der die Abmischung übernahm. Im Sommer 2012 kam das Album unter dem Titel Kings Will Fall auf den Markt und konnte den Erfolg der ersten Platte wiederholen. Neben weiteren Club- und Supportauftritten bekam man auch einen Slot auf dem Wacken Open Air 2012. Es folgten Auftritte auf weiteren Festivals wie dem Ragnarök-Festival, Beastival sowie als Teil des Heidenfest-Ensemble.

Drittes Album, Europatouren und Besetzungswechsel

Mit dem 2014 über NoiseArt Records erschienenen dritten Studioalbum Cathyron begleiteten Winterstorm als Support Van Canto auf der Tour of the Brave durch Deutschland und Teile Europas. Im Anschluss war die Gruppe erneut quer durch Europa auf der Heidenfest-Tour unterwegs. Im Dezember 2015 gab die Band bekannt, dass Sebastian Albrecht und Armin Haas aus der Band ausscheiden. Eine Zusammenarbeit mit Albrecht war nach Bandangaben wegen „unterschiedliche Auffassungen vom Musikgeschäft“ nicht mehr möglich, während sich Armin auf das Komponieren statt Musizieren sowie außermusikalische Tätigkeiten konzentrieren will, jedoch der Band weiterhin beratend zur Verfügung stehen wird. Wenige Tage später wurden Tobi Lodes als neuer Gitarrist und Jonas Hack als neuer Schlagzeuger vorgestellt. Es folgten mehrere Auftritte unter anderem auf dem Rock Harz Open Air 2016.

Viertes Album

Das vierte und bisher erfolgreichste Album "Cube of Infinity" erschien am 19. August 2016 auf dem Summer Breeze Open Air und stieg auf Platz 31 der offiziellen deutschen Album-Charts. Nach weiteren Touren durch Deutschland folgten sämtliche Auftritte auf Festivals wie Rock Harz Open Air, Christmas Bash und erneut Summer Breeze Open Air.

Die Band Winterstorm ist seit 2019 beim Plattenlabel AFM unter Vertrag.

2021 verließ Tobias Lodes, welcher nebenbei auch bei Beyond the Black aktiv ist die Band aus zeitlichen Gründen. Er wurde durch Jochen Windisch ersetzt.