Hljómsveitin Nightwish var stofnuð í júlí 1996 af hljómborðsleikaranum Tuomas Holopainen. Hann fékk með sér gítarleikarann Emppu Vuorinen, söngkonuna Tarja Turunen. Saman mynduðu þau hljómsveit sem spilaði acoustic lög. Fyrstu þrjú lög hljómsveitarinnar voru tekin upp í Október – Desember sama ár.

Lögin hljómuðu ekki eins vel og þau vildu og fengu þau trommarann Jukka Nevalainen til liðs við sig og þau notuðu rafmagnsgítar í staðinn fyrir acoustic gítar. Eftir nokkrar vikur af æfingum fóru þau í studio og tóku upp nokkur lög sem finna má á Angels Fall First limited edition plötunni.

Í maí 1997 undirritaði Nightwish plötusamning við Spinefarm sem hljóðaði upp á tvær plötur. Í ágúst fór Nightwish í studio og tóku upp fjögur ný lög. Áður en Angel Fall First var gefin út, var gefin út smáskífa við lagið The Carpenter sem náði hæst númer átta á finnsku topplistunum. Angels Fall First var gefin út í byrjun nóvember 1997 sem náði best númer 31 á finnsku topplistunum.

Nightwish spiluðu á sínum fyrstu tónleikum í Kitee þann 31. desember 1997. Eftir það spiluðu þau aðeins sjö sinnum þennan sama vetur. Ástæðan var sú að Jukka og Emppu voru í báðir í hernum og Tarja var upptekin við námið. Spinefarm lengdi samninginn við Nightwish úr tveimur plötum upp í þrjár.
Í apríl 1998 hófust tökur á fyrsta myndbandinu við lagið The Carpenter.

Um sumarið sama ár fengu þau bassaleikarann Sami Vänskä. (ATH. Þau voru ekki með bassaleikara áður). Um sumarið tóku þau upp og æfðu nokkur lög fyrir nýja plötu og fóru í stúdíó í ágúst mánuði. Upptökunum lauk um miðjan október. 13. nóvember hófust tökur á öðru video við lagið Sacrament Of Wilderness. Smáskífan var gefin út 26. nóvember og ný plata sem heitir Oceanborn kom út 7. desember.

Platan fékk frábæra dóma og lenti hún í fimmta sæti á finnsku topplistunum og smáskífan Sacrament of Wilderness var númer eitt í margar vikur. Veturinn 1999 voru þau stanslaust á tónleikum um Finnland. Um vorið var svo Oceanborn gefin út um gjörvallann heim og héldu þá tónleikar þeirra áfram. Á sama tíma var smáskífan Sleeping Sun tekin upp. Í ágúst var hún gefinn út í Þýskalandi þar sem 15000 eintök voru seld. Á sama tíma tilkynntu Nightwish að þau mynda fara í 26 daga Evróputúr með þýska bandinu Rage.

Í byrjun ársins 2000 fóru Nightwish aftur í stúdíó til að taka upp nýja plötu en þau voru líka að taka þátt í undankeppni Eurovision með lagið Sleepwalker en töpuðu.

Nýja platan, Wishmaster var gefin út í maí og hófst túrinn í heimabæ Nightwish Kitee og eftir tónleikana fengu þau afhent gull plötu fyrir Oceanborn og smáskífurnar. Wishmaster fór beint á toppinn á finnsku topplistunum. Wishmaster túrinn var frá Finnlandi til Suður Ameríku þar sem þau eyddu þremur vikum að spila í Brasilíu, Argentínu o.fl stöðum. Næsta verkefni var að gera live disk. Tónleikarnir sem voru teknir upp 29. desember í Tampere. Diskurinn var svo gefinn út sumaroð 2001.

Í mars 2001 fóru Nightwish í stúdíó til að taka upp lag Gary Moore, “Over The Hills And Far Away”, ásamt tveimur nýjum lögum og endur gerð lagsins “Astral Romance” sem finna má á Angel Fall First. Nightwish framlengdi aftur samninginn við Spinefarm til að gera eina plötu til viðbótar sem átti að koma út sumarið 2002.
Á þessum tíma voru Nightwish alveg við það að hætta og Tuomas sem satt best að segja vildi að bandið hætti ákvað að einhver þyrfti að fara og Sami Vänskä var rekinn. Við tók Marco Hietala. King Foo Entertainment varð bókunar aðili og Ewo Rytkönen kunningi Tuomas tók við starfi umboðsmanns. Upptökur á nýrri plötu Century Child hófust svo í janúar 2002.

Fljótlega eftir upptökur kom út smáskífan Ever Dream sem fór í gull í Finnlandi á innan við 2 daga. Nightwish tilkynntu einnig að eftir “Century Child World Tour 2002” myndu þau taka sér frí. Century Child kom út í maí 2002 seldist í gull á tveimur klukkutímum í Finnlandi. Í Þýskalandi endaði platan númer fimm og númer fimmtán í Austurríki. til, til að mynda voru meðlimir Nightwish að spila með öðrum böndum, nema Tarja sem var að Í byrjun ársins 2003 var unnið hörðum höndum við að gera heimildarmynd sem gefin var út á DVD. Myndin sem kom út 6. október 2003 ber heitið “End Of Innocence”. Nightwish voru fljótlega kominn aftur í studio til að taka upp sína fimmtu plötu “Once”.


Árið 2004 var beðið með eftirvæntingu af aðdáendum og af hljómsveitinni. Þreytandi stúdíó tímar voru farnir að segja til sín líkamlega og andlega. Upptakan fór fram í Phoenix stúdíóinu í London. Með í stúdíóinu var sinfóníu hljómsveit Lundúna.
”Nemo” var fyrsta smáskífan af plötunni og var myndbandið tekið upp fljótlega eftir að upptökur á Nemo voru búnar.Nightwish skrifuðu undir samning við Nuclear Blast sem eyddi miklum peningum auglýsa Nightwish.

”Once” fór í gull sama dag og hún var gefin út og það gerði ”Nemo” einnig. Once túrinn mun innihalda 150 tónleika um allan heim. Túrnum mun ljúka seint 2005. Lengsti túr í sögu Nightwish.