A Nightwish ötlete 1996-ban született, mikor Tuomas barátaival egy tábortűz mellett ült. Az első három dalt 1996 októbere és decembere között vették fel, ezeket még akkusztikus hangszereken játszották. Ebben az időben a csapatnak három tagja volt: Tuomas, Tarja, és Emppu.
Az együttes neve, "Nightwish" éjjeli kívánságot jelent. Ilyen formában több számukban is megjelenik a szókapcsolat.

Aztán úgy gondolták, szükségük van egy dobosra is. Ezért csatlakozott hozzájuk Jukka, az akkusztikus gitárt pedig lecserélték elektromosra. Néhány hét gyakorlás után, 1997 áprilisában stúdióba vonultak. Ekkor felvettek hét dalt, amelyek az Angels Fall First album limitált kiadásán találhatóak.

1997 májusában a Nightwish aláírt egy két lemez elkészítéséről szóló szerződést a Spinefarm kiadóval.  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ímű dal bekerült a nyolc legjobb szám 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 kezdték az első videoklip, 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. A következő nyáron csatlakozott a basszista Sami Vanska az együtteshez.
Augusztus elején stúdióba vonultak . 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 videoklipjét. Ennek a dalnak a kislemeze november 26.-án jelent meg, az új albumot pedig Oceanborn-nak nevezték el, amely december 7-én jelent meg.

Az Oceanborn sikerén mindenki meglepődött. A finn albumok hivatalos listáján az ötödik helyre küzdötte fel magát, és a Sacrament Of Wilderness hetekig 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 List Chart Show-ban is. Tavasszal az Oceanborn-t kiadták külföldön is. Májusban a zenekar ismét koncertezni indult, ami alatt két országot bejártak, és majdnem az összes rockfesztiválon játszottak. Ebben az időben felvették a Sleeping Sun című 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ímű 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. Akkoriban 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 2000 júniusában Dél-Amerikában. A három hetes koncertturné 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ű művének feldolgozása is. Ezen az albumon már az új basszusgitárosuk, 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 egy ideig 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.

A csapat elkészítette negyedik stúdió albumát, mely a Once címet viseli.
Ehhez már elkészült az első videoklip is, Nemo címmel. 
A korongon nagyzenekari kísérettel játszanak, egy szerzemény pedig egy film betétdala lesz.
Az együttes 2004. május 22-én egy hatalmas show-val egybekötött lemezbemutató koncertet adott a Kitee-i jégcsarnokban.