A Nightwish ötlete 1996 egyik éjjelén született, mikor Tuomas barátaival a tábortűz körül ült. Az első három dalt 1996 októbere és decembere között vették fel, ezeket még akusztikus hangszereken játszották. Ebben az időben a csapatnak három tagja volt: Tuomas, Tarja, és Emppu.

Jött az ötlet: legyen dobosuk. így csatlakozott hozzájuk Jukka, az akusztikus gitárt pedig lecserélték elektromos gitárra. Néhány hét gyakorlás után stúdióba vonultak, 1997 áprilisában. Ekkor felvettek hét dalt, amelyek az Angels Fall First album korlátozott kiadásán találhatóak.

1997 májusában a Nightwish aláírt egy szerződést a Spinefarm kiadóval, két lemez felvételére. Augusztusban stúdióba mentek és rögzítettek négy új dalt. Mielőtt az Angels Fall First album megjelent volna, a The Carpenter c. dal bekerült a nyolc legjobb közé a finn hivatalos slágerlistán. Ugyanezen a listán a legjobb 31-be került az Angels Fall First album, amit november elején adtak ki.

A Nightwish első fellépése 1997. december 31.-én volt, Kitee városában. Ezen a télen a Nightwish csak hét koncertet adott, mert Jukka és Emppu sorkatonai szolgálatát töltötte, Tarját pedig lekötötték tanulmányai.

1998 áprilisában elkezdték az első videoklipp, a The Carpenter forgatását. Ezt május elején bemutatták Jyrki-ben (egy TV műsorban). Tuomas és Tarja interjút is adott ekkor. A következő nyáron a basszista Sami Vanska csatlakozott a csapathoz. Nyáron az új dalokat gyakorolták, majd stúdióba vonultak augusztus elején. A felvételek október végére készültek el. November 13.-án a Nightwish Kitee-ben koncertezett, itt készítették a Sacrament Of Wilderness videoklippjét. Ennek a dalnak a kislemeze november 26.-án jelent meg, az új albumot pedig Oceanborn-nak nevezték el. Ez december 7.-én jelent meg.

Az Oceanborn sikerén mindenki meglepődött. A finn albumok hivatalos listáján az ötödik helyre ért fel, és a Sacrament Of Wilderness hetekig az első volt a kislemez listán. 1999 telén három hónap alatt a Nightwish számtalan koncertet adott országszerte, ezenkívül szerepelt a Lista Chart Show-ban is. Tavasszal az Oceanborn-t kiadták külföldön is. Májusban a zenekar ismét koncertezni indult, két országot bejártak, majdnem az összes rock fesztiválon játszottak. Ebben az időben felvették a Sleeping Sun c. kislemezt. Augusztusban ezt kiadták Németországban, ezen még megtalálhatóak voltak a Walking In The Air, Swanheart és az Angels Fall First c. dalok is. Németországban csak ebből a kislemezből 15.000 példány fogyott el egy hónap alatt. Augusztusban értesültek, hogy az Oceanborn és a Sacrament Of Wilderness aranylemez lett. Ekkoriban 26 koncerten vettek részt Európában a Rage nevű német zenekarral.

2000 elején a banda ismét stúdiómunkába kezdtett, elkezdték harmadik album felvételeit. A munkát kisebb megszakításokkat végezték, mivel közben a finn Eurovíziós Dalfesztiválon is szerepeltek a Sleepwalker c. dallal. A Nightwish már az első körben bejutott a döntőbe, de az elsöprő közönségszavazat ellenére csak a második helyet kapta.

Az új albumot, a Wishmaster-t májusban adták ki. A Wishmastour Kitee-ből indult. A show után a Nightwish átvette az Oceanborn-ért, a Sacrament Of Wilderness-ért, a Walking In The Air-ért és a Sleeping Sun-ért járó aranylemezeket. A Wishmaster egyből a finn albumok toplistája első helyére ugrott, és ott is maradt három hétig. Közben ez a lemez is aranylemez lett. A rajongók és a média is egyetértett abban, hogy ez az album legyen a hónap albuma a német Rock Hard magazin 2000 júniusi számában, Bon Jovi és az Iron Maiden ekkor megjelenő lemezei mellett.

A Wishmaster a német lista 21., és a francia toplista 66. helyezését érte el. A Wishmaster World Tour, ami Kitee-ből indult, elsőként a nagy fesztiválokon folytatódott Finnországban, majd Dél-Amerikában 2000 júniusában. A három hetes koncert turné Brazíliában, Chilében, Argentínában, Panamában és Mexikóban úgy végződött, hogy a csapat a legpozitívabb tapasztalatai közt tartja számon. Ezt sikeres koncertek követték a Wacken Open Air-en, a Biebop Metal Festival-on és az első európai turnén a Sinergy-vel és az Eternal Tears Of Sorrow-val. Novemberben a Nightwish két koncertet is adott a kanadai Montrealban.

A Nightwish következő terve egy teljes koncert DVD és VHS kiadása, továbbá egy limitált példányszámú CD volt, melyet csak Finnországban lehet kapni. A DVD és VHS anyaga végül a 2000. december 29.-én előadott tamperei koncert lett. Az anyag 2001 áprilisában jelent meg Finnországban és 2001 nyarán világszerte. A koncert végén a Nightwish tagjai átvették a Wishmaster-ért járó platina-, és a Deep Silent Complete-ért járó aranylemezt.

2001 márciusában a Nightwish tagjai ismét stúdióba vonultak, hogy rögzítsék Gary Moore klasszikus Over The Hills And Far Away c. dalát, két új dallal és az Astral Romance újrafelvételével egyetemben. A végső verzió 2001 júniusában jelent meg. A német (Drakkar) verzió tartalmaz hat koncertfelvételt is.

Az Over The Hills And Far Away után következett egy limitált példányszámú kiadvány, mely az első négy korongot tartalmazza, díszcsomagolásban. A CD-ken Tarja arcának részletei láthatók, a belső borító beillik egy kisebb könyvecskének is.

A Nightwish ismét aláírt egy szerződést a Spinefarm Kiadóval egy albumra vonatkozóan, mely 2002 nyarán jelent meg. Ez az album lett a Century Child, melyen többek közt szerepel Webber The Phantom Of The Opera c. művének feldolgozása is. Ezen az albumon már az új basszerük, Marco Hietala játszik, sőt néhol Tarjával duettezik. A stílus kicsit kiforrottabb, de sokak szerint nem az, amit a Nightwishtől megszoktak.

A csapat most visszavonult, mert Tarja operaénekesnőnek tanul, a többiek pedig az új album anyagán dolgoznak.

2003. június 5-én a Nightwish Magyarországra látogatott, a Summer Rocks fesztivál keretében.

Már megvásárolható a Nightwish új koncert DVD-je, End Of Innocence címmel.

A csapat készíti negyedik stúdió albumát, mely a Once címet viseli. Ehhez már készül az első videoklip is, Nemo címmel. Az együttes 2004. május 22-én egy hatalmas show-val egybekötött lemezbemutató koncertet ad a Kitee-i jégcsarnokban. Jegyeket márciustól lehet kapni a Nightwish hivatalos honlapján.