Hudební tvorba skupiny měla původně zahrnovat písně, které by se daly zpívat u táboráků. Jelikož byl však Tarjin hlas pro tyto účely příliš mohutný, byly do skladeb zahrnuty metalové prvky. V květnu 1997 podepsala kapela smlouvu na dvě alba s finskou nahrávací společností Spinefarm Records. Deska Angels Fall First byla vydána v listopadu téhož roku a ve finském hudebním žebříčku se umístila na 31. příčce. Hudební kritici přijali album rozporuplně – zatímco někteří ho hodnotili jako silně podprůměrné, jiní ho vychvalovali až do nebes.
Po natočení videa k úspěšné písni The Carpenter vydala kapela album Oceanborn, následovníka desky Angels Fall First. Po stránce aranží a textů bylo Oceanborn propracovanější a progresivnější než jejich první album. Podle samotných členů kapely bylo album Oceanborn technicky nejnáročnější album, které natočili. Ve dvou písních se tu objevil i Tapio Wilska, bývalý člen Finntroll. Deska ve finské hitparádě alb dosáhla na 5. místo. Na desce se objevil například single Walking in the Air.
V roce 1999 vydali Nightwish k příležitosti zatmění Slunce v Německu singl Sleeping Sun. Během prvního měsíce se ho prodalo 15 000 kopií. O rok později se Nightwish s písní Sleepwalker účastnili finské kvalifikace na Eurovision Song Contest, v níž skončili na druhém místě. Když v roce 2006 vyhrála finská metalová skupina Lordi celou Eurovizi, ptali se v jednom rozhovoru Tuomase, jestli si myslí, že Nightwish by byli lepší. Tuomas odpověděl, že toho nelituje; Lordi jsou prý skvělí a je pyšný na to, že mohli ukázat, co Finsko dokáže.
V květnu vydala kapela album Wishmaster, které okamžitě vyletělo na 1. místo v prodejnosti alb a zůstalo tam tři týdny. Během této doby bylo oceněno jako zlaté. Navzdory dlouho očekávaným vydáním alb skupin Iron Maiden či Bon Jovi, která vyšla současně s ním, získal Wishmaster v německém časopise Rock Hard titul album měsíce.
V roce 2002 vydali Nightwish album Century Child a singly Ever Dream a Bless the Child. Hlavní rozdíl mezi tímto a předchozími alby byl v tom, že v písních Bless the Child, Feel For You, Ever Dream a Beauty of the Beast, byl použit finský symfonický orchestr, aby se tak ještě více rozšířil existující pocit klasické hudby. Trvalým favoritem fanoušků se však stala cover verze písně The Phantom of the Opera, ze slavného stejnojmenného muzikálu, který zkomponoval Andrew Lloyd Webber.
Nové album, pojmenované Once bylo vydáno v červnu 2004, společně s prvním singlem Nemo (latinsky „nikdo“). Singl dosáhl vrcholu v hitparádách ve Finsku a Maďarsku a stal se jejich nejúspěšnějším vydaným singlem. Once využívá v devíti skladbách celého orchestru. Na rozdíl od Century Child se členové Nightwish tentokrát rozhodli najít orchestr za hranicemi Finska. K nahrání alba byl proto vybrán London Session Orchestra. Je to také jejich druhé album, kde se objevuje píseň napsaná celá ve finštině - Kuolema Tekee Taiteilijan (v překladu Smrt dělá umělce). Once získalo ve Finsku třikrát platinovou desku.
V roce 2005 byla z kapely vyhozena Tarja Turunen a členové skupiny vyhlásili casting na hlavní zpěvačku. Otevřeni byli všem hudebním stylům. Jedinou podmínkou bylo to, že zpěvačka musí mít dostatečně dynamický a přizpůsobivý hlas. Identita nové zpěvačky byla zveřejněna den před vydáním prvního singlu z alba Dark Passion Play, tedy v květnu 2007. Náhradnicí se stala tehdy pětatřicetiletá Anette Olzon z Katrineholmu ve Švédsku. Další album pojmenované Imaginaerum vyšlo v listopadu 2011. Album je v podstatě soundtrackem ke stejnojmennému filmu a prolíná se tak s jeho příběhem. Film je o starém umírajícím hudebním skladateli a poetovi Thomasi Whitmanovi (kombinace jmen Tuomase Holopainena a amerického basníka Walta Whitmana - Tuomasova oblíbeného autora), který vzpomíná na své mládí a dětství. Stejnojmenný film režíroval Stobe Harju, který již s Nightiwish spolupracoval na klipu ke skladbě The Islander.
V říjnu 2012 skupina skrze svůj profil na Facebooku oznámila, že se s Anette dohodla na konci jejího působení v kapele. Podle tiskového prohlášení bylo čím dál tím víc zřejmé, že směřování kapely je v konfliktu s jejími potřebami. A tento konflikt vedl k rozdělení, ze kterého se již nebylo možné vrátit zpět. Po zbytek koncertního turné nazvaného Imaginaerum World Tour zastoupila Anette nizozemka Floor Jansen, která se v říjnu 2013 stala oficiální zpěvačkou kapely. Zároveň byl do kapely přijat i Troy Donockley, který doprovázel skladby Nightwish na flétny a dudy.
