Группа Stratovarius была основана в январе 1984 года в Финляндии под именем Black Water («Чёрная вода»). Считаются одними из основоположников направления пауэр-метала. Группа прошла через множество изменений в составе и в характере исполняемой музыки, прежде чем обрела свой стиль. Основателями группы были Туомо Лассила, Стаффан Стрелман, и Джон Виерве. В 1985 году в группу пришёл Тимо Толкки, заменив Стрелмана на месте гитариста, изменил название группы на Stratovarius (объединение слов Stratocaster и Stradivarius) и взял на себя роль вокалиста. Толкки стал движущей силой и идеологом группы, осуществляя практически полный контроль над созданием песен. Он принёс в звучание группы не только тяжесть рока, но и элементы неоклассического металла. В 1987 году группа разослала демозапись по различным звукозаписывающим компаниям, в итоге подписав контракт с CBS Finland. В 1989 году был выпущен первый альбом группы, Fright Night, сопровождаемый двумя синглами.
После расставания с CBS группа претерпела несколько изменений в составе, но смогла выпустить второй альбом Stratovarius II на Bluelight Records. Позже альбом был переиздан как Twilight Time компанией Noise Records. В 1994 выходит третий альбом, Dreamspace, при участии нового басиста, Яри Кайнулайнена, который вошёл в группу, когда альбом был записан уже более чем на 70 %. Толкки принимает решения прекратить выступать в роли вокалиста, и группа приглашает нового вокалиста, Тимо Котипелто. Выход альбома Fourth Dimension в 1995 году стал большим успехом для группы, но внутренние разногласия, особенно из-за стиля музыки, которого придерживался Толкки в написании песен, привели к уходу одного из основателей группы, Туомо Лассилы и клавишника Антти Иконена.
Места ушедших музыкантов заняли соответственно немецкий барабанщик Йорг Михаэль и шведский клавишник Йэнс Юханссон, работавший ранее с Ингви Мальмстином. В создании своего пятого альбома, Episode, Stratovarius нашёл, наконец, своё фирменное звучание и собрал сильный и разносторонний состав. Episode, вышедший в 1996 году был большим проектом, с участием большого хора и струнного оркестра. Альбом стал новым серьёзным успехом группы, и многие фанаты считают его лучшим альбомом Stratovarius.
В таком неизменном составе группа выпустила три весьма успешных альбома в течение нескольких лет: Visions в 1997 году, Destiny в 1998 году, и Infinite в 2000 году. С каждым альбомом росла известность группы и армия её поклонников, появляются большие фан-клубы за пределами Скандинавии, особенно популярна группа стала в Японии.
В 2003 году, Stratovarius выпускают свой самый эпический проект: двойной альбом, названный Elements. В этих двух альбомах группа достигла вершины в своём прогрессивном и симфоническом стиле пауэр-метала. Первая часть дилогии, Elements, Pt. 1, была издана в начале 2003 года, сопровождаемая мировым турне. За Elements, Pt. 1 последовала вторая часть, Elements, Pt. 2, вышедшая на том же лейбле Nuclear Blast в этом же году.
В конце 2003 года в группе произошёл раскол: Тимо Котипелто и Йорг Михаэль покинули группу после очень смутно объяснённого конфликта. Толкки приглашает Катрийну «Miss K» Вийалу на роль вокалистки, и Андерса Йоханссона (брата Йэнса) из группы Hammerfall как сессионного барабанщика. Весь остаток 2004 года был покрыт молчанием о состоянии дел в группе.
Тимо Толкки, опубликовавший на сайте Stratovarius несколько странных заявлений, был госпитализирован и прошёл курс лечения от психической болезни. В январе 2005 года было объявлено, что Stratovarius воссоединился в своём прежнем составе. В июне 2005 года Толкки объявил, что басист группы, Яри Кайнулайнен, покинул группу по личным причинам. С тех пор и поныне бас-гитаристом Stratovarius является Лаури Порра.
В сентябре 2005 года Stratovarius выпускает одноимённый альбом, Stratovarius (ранее в альбоме Fourth Dimension была инструментальная композиция «Stratovarius»). В это же время Stratovarius начинают большой мировой концертный тур, стартовавший в Аргентине, включивший Северную Америку, где впервые в истории группа гастролировала по США и Канаде. Они давали концерты на таких мероприятиях, как Atlanta’s «Prog Power», и в таких известных залах, как B.B. King’s House Of Blues в Нью-Йорке и «Trocadero Theatre» в Филадельфии. Турне также включило концерты в европейских и японских городах.
В 2007 году группа начала было работу над новым, двенадцатым студийным альбомом (под рабочим названием R…. R…..), для которого было написано одиннадцать треков и который планировался к выходу в январе 2008 года. Тимо Толкки заявил, что альбом выйдет перед «массовым мировым туром». Однако альбому так и не суждено было выйти, в апреле 2008 года Тимо Толкки опубликовал объявление, в котором говорится, что Stratovarius прекратил своё существование. В открытом письме Толкки обвинил Тимо Котипелто и Йорга Михаэля в частых конфликтах друг с другом и с ним самим. Он также заявил, что творчество группы зашло в тупик и превратилось в чисто коммерческое.
Я отлично помню, как мы играли эти старые вещи раньше, и то, как мы играли их сейчас, означало лишь то, что у группы больше нет души. Я посмотрел по сторонам и почувствовал себя частью машины, и не было никаких новых ощущений, а то, что я делал, не доставляло никакой радости. Группа звучала ужасно. Никто не вкладывал душу в игру. Мы играли всё те же старые песни.
Практически все песни, написанные Тимо Толкки для незаконченного альбома Stratovarius, были выпущены на альбоме New Era его нового проекта Revolution Renaissance.
Остальные участники группы отреагировали ответным письмом, в котором обвинили Толкки в жадности и поспешили опровергнуть заявление о распаде группы. Котипелто, Михаэль, Порра и Йоханссон, подписавшиеся под письмом, собираются продолжать выступления под названием Stratovarius, на что Толкки дал добро, отказавшись от прав на название.
Тимо Котипелто: «Конечно, нам сейчас сложнее, чем, скажем, три года назад, когда группой заправлял мистер Толкки. Он писал музыку, занимался продюсерской работой — и, надо признать, был в этом очень хорош. Он решал все вопросы. Трудно было лишь одно: играть с ним в одной команде. Сложный человек, у которого семь пятниц на неделе, который меняет своё мнение пять раз за три минуты. Нормально работать под его началом просто нереально. Сейчас… да, какие-то вопросы решаются сложнее, но это не так уж важно. Главное в другом: я снова начал чувствовать вкус к жизни — такая эйфория, как в пятнадцать лет, когда ты только начинаешь открывать для себя радости взрослой жизни. Как никто другой, я понимаю: главное — это настроение в команде, общее желание творить, энтузиазм, удовольствие, чтобы самих музыкантов перло от того, что они делают. И никакой внутренней гнили. Лучше не делать ничего, чем делать что-то без души.»
23 августа 2008 года было объявлено, что место Тимо Толкки на гитаре займет Матиас Купиайнен, который был, по словам участников группы единственным кандидатом и имел за плечами опыт изучения музыкальной теории и музыкальных технологий в таких учебных заведениях, как Академия Сибелиуса. В марте 2009 года группа в обновлённом составе выпустила альбом Polaris и отправилась в международное турне в его поддержку. В мае 2009 года Stratovarius выступили в Москве и Санкт-Петербурге.
В начале 2011 году группа выпустила альбом Elysium.
15 сентября 2011 года на официальном сайте группы появилась информация о том, что группу из-за тяжёлой болезни покидает барабанщик Йорг Михаэль, игравший с очень многими коллективами, но при этом посвятивший группе 15 лет. Прощальные концерты с Йоргом состоялись в конце 2011 года. Концертная деятельность была приостановлена в связи с поиском нового барабанщика. 22 июня 2012 года Stratovarius объявили имя нового участника группы. Им стал финский барабанщик Ролф Пилве, известный ранее по работам с Solution .45, The Magnificent и Dreamtale.
Первым студийным альбомом, записанным при участии нового барабанщика, стал Nemesis, выпуск которого состоялся 22 февраля 2013 года.
11 сентября 2015 года вышел альбом Eternal.
