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, 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 awayc. 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 ekkor 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. A nagy sikerű Kitee-i koncert után hamarosan megjelenik a Nightwish ötödik nagylemeze, a Once. A korongon nagyzenekari kísérettel és kórussal játszanak, a Wish I had an Angel pedig egy betétdal lesz az Alone in the Dark c. mozifilmben. 

Az ötödik album az európai Billboard listán az első helyet szerezte meg. Az albumon Marco sokat énekel, míg Tarja inkább lágy hangon játszik közre, és a legjelentősebb szerep a nagyzenekarnak jut. A Dark Chest of Wonders, Wish I Had An Angel, Planet Hell nagyszerű dallamait felülmúlja a Ghost Love Score, mely egy kisebbfajta opera. A jó előre beharangozott a Nemo inkább a nagyközönség igényeit elégíti ki - a videoklipjén már látszik a magasabb költségvetés, azonban még mindig nem képes a zenekar megszabadulni a berendezett stúdiójelenetek alkalmazásától.

A zenekar fél éven belül két nagy sikerű koncertet is adott Budapesten. 2005. október 23-án megtartották a Once turné legutolsó és egyben leghatalmasabb, -látványosabb koncertjét a Hartwall Arénában, Finnországban - az anyag rögzítésre került. A koncert után közvetlenül a Nightwish tagjai nyílt levélben szólították fel Tarját a távozásra, különösen személyes, de üzleti okokra is hivatkozva. Legnagyobb problémájuk Tarja férje, és egyben menedzsere jelenléte, és az, hogy szerintük nagyon megváltoztatta a régen oly szeretnivaló lányt. 

Tarja két nappal a levél megjelenése után szintén nyílt levéllel válaszolt. A kedélyek sokáig nem csillapodtak. Megtudhattuk, hogy egyik fél sem hagyja abba a zenei karriert - a zenekar új énekesnőt kezdett keresni világszerte, Tarja fiútestvére albumán működik közre, és aláírta első szólólemezésről szóló szerződését a Universal Music kiadóval.

Közben a DVD megjelenése elől is elhárultak a jogi akadályok, és június 2-a óta megvásárolható az anyag, amiről nyugodt szívvel állíthatjuk, hogy profi munka: fantasztikus hangzás és képi világ, effektek és felvételek, és megdöbbentő extra film található rajta. 

Tuomas több interjúban említette, hogy az összes új dal kész van már, mintegy 15 darab. Szeptemberben vonulnak stúdióba, hogy rögzítsék a zenéket, az új énekesnővel pedig decemberben szeretnének elkezdeni dolgozni, így az új album 2007 közepére várható.