A Stratovariust 1984-ben, Helsinkiben alapította Tuomo Lassila énekes/dobos, John Viherva baszusgitáros és Staffan Strihlman gitáros. Ők már előzőleg is együtt zenéltek Black Water néven. A maitól teljesen eltérő, Black Sabbath hatású zenét játszottak. John Viherva 1984 végére kilépett a zenekarból, az új bőgős Jyrki Lentonen volt, aki előzőleg Timmo Tolkki-val együtt zenélt a Road Block nevű zenekarban.

1985-ben Staffan Strihlman váratlanul kilépett a zenekarból, helyére Timo Tolkki-t hívták. Tolkki az énekes szerpét is átvette, a zene dallamosabbá vált, előtérbe kerültek a klasszikus zenei hatások. Az elkövetkezendő időket sűrű koncertezéssel töltötték, majd 1987-ben felvették első demojukat, amin szerepeltek a Future Shock, Fright Night és Night Screamer dalok is. A demo eredményeként a CBS Finnland szerződtette őket. A felállás kiegészült Antti Ikonen szintetizátorossal.

Néhány EP után, 1989-ben megjelent a Fright Night című első albumuk. 1989 vége koncertezéssel telt, felléptek a Giants Of Rock fesztiválon is az Anthrax és egyéb neves zenekarok társaságában. A fesztivál után Jyrki Lentonen kilépett a zenekarból, így a következő, Twilight Time albumon Tolkki basszusgitározott, bár a borítóban Jari Behm szerepel, aki valójában nem játszott az albumon.

Átszerződtek a Shark Records-hoz, majd 1992-ben megjelent a Twilight Time album. Japánban az album 5 hónapig szerepelt az import albumok Top 10-es eladási listájában. 1993-ban ez az album fogyott az import albumok közül a legnagyobb példányszámban Japánban. Az 1993-as év új dalok írásával telt, japánban szerzőzdtette őket a JVC Victor lemezkiadó társaság. A zenekarba új basszusgitáros érkezett, Jari Kainulainen.

1994 elején megjelent a Dreamspace album. Az albumon Tuomo Lassila betegsége miatt négy számban Sami Kuoppamäki ült a dobok mögött. Mind a kritikusok, mind a rajongók lelkendezve fogadták az új anyagot. Júniusban a zenekar Japánba is eljutott, felléptek Tokyo-ban, Osaka-ban és Nagoya-ban. 1994 nyarán Tolkki felvette első szólóalbumát, a Classical Variations and Themes-t. Elhatározta, hogy ez után a Stratovarius-ban többé nem énekel, így a zenekar énekes után nézett.

Az 1995-ös Fourth Dimension albumon már Timo Kotipelto énekelt. Ezzel az albummal a Stratovarius megduplázta a Dreamspace eladási eredményeit. Ezután turné következett, felléptek Németországban, Hollandiában, Svájcban, Finnországban, Görögországban és Japánban. A turné után személyi és zenei ellentétek miatt Tuomo Lassila és Antti Ikonen kilépett a zenekarból, mivel nem akarták Tolkki zenéjét játszani. Az új szintis Jens Johansson lett, a dobok mőgé pedig Jörg Michael ült.

Az ötödik albumot, az Episode-ot a Finnvox studiókban vették fel. Ez az album óriási előrelépést jelentett a zenekar számára. Jens és Jörg belépésével a hangzás tisztult, az eredmény egy drámai, dallamos, szimfonikus metal album lett. Az albumra a szimfonikus betéteket egy 40 fős kórus és 20 vonós játszotta fel.

A következő album, a Visions 1997 áprilisában jelent meg, és a finn eladási listán az 5. helyről indult és 24 hetet töltött a Top 40-ben. A megjelenés után óriási turnéra indultak Európában, Japánban és Dél-Amerikában. A Visions finnországban aranylemez lett.

A turné alatt rögzítették a Stratovarius első koncertalbumát, a dupla Visions Of Europe-t, amely 1998-ban jelent meg. Az album több mint 100 perc zenét tartalmazott, és hatalmas sikert aratott mind a kritikusok, mind a rajongók körében.

A koncertalbum megjelenése után ismét a Finnvox studioban álltak neki a Destiny album felvételének. Az album még 1998 végén megjelent, és már a meg jelenés előtt (!) a finn toplista első helyére került. Hamarosan ez az album is bearanyozódott. Az 1999-es esztendő további sikereket is hozott a Stratovarius-nak, a finn „Suomi Finland Perkele” magazin olvasói az év legjobb zenekarának választották, és az SOS klipp lett az év hazai videoklippje ugyanezen szavazás alapján, ezenkívül több magazinban is előkelő helyezéseket értek el. 1999 nyarán Japán kivételével a Nuclear Blast-hoz szerződtek.

A kiadóváltás előtt a Noise Records-nál még megjelent egy válogatásuk, a The Chosen Ones. A válogatoáson szerplő dalokat a rajongók szavazása alapján állították össze. 1999 végét a zenekar ismét studióban töltötte, majd 2000 elején megjelent az Infinite album. Az album megjelenését minden eddiginél nagyobb turné követte, 25 országban 82 koncertet adtak. A koncertsorozat közben, a Wacken Open Air-on Timo Kotipelto kezét megégette a pirotachnika, ami miatt a Dél- Amerikai turnét későbbre halasztották. Az Infinite is aranylemez lett.

2000 végén jelent meg első homevidojuk, az Infinite Visions, amely több mint két órás, és koncertrészleteket, klippeket és a turné eseményeit tartalmazza. A sok koncert és a megfeszített munkatempó kimerítette a zenekart, így úgy döntöttek, két év pihenőt tartanak.

2001 elején megjelent az Intermission, ami csak japánban megjelent bonustrackeket, feldolgozásokat és egyéb érdekességeket tartalmaz. A következő igazi studióalbum 2003 elejére várható. Addig is Tolkki és Kotipelto is szólóalbumot készít.