A Nightwish ötlete 1996-ban fogant meg Tuomas gondolataiban, egy júliusi éjen, melyet a tábortűz fénye és a barátok jelenléte ragyogott be. Az első három akusztikus dalt még ez év utolsó 3 hónapjában rögzítették. Ekkoriban még mindössze három tagja volt a zenekarnak: Tuomas, Tarja és Emppu.
Később kíváncsiak lettek, hogyan szólnának a dalok dobkísérettel - ekkor csatlakozott a zenekarhoz Jukka - majd az akusztikus gitárt is felváltotta az elektromos hangszer. Néhány hét felkészülés után, 1997 áprilisában a zenekar stúdióba vonult, és hét dalt vett fel, melyek az Angels Fall First album korlátozott példányszámú kiadásán hallhatók.
1997 májusában a Nightwish két lemezre szóló szerződést kötött a Spinefarm kiadóval, majd augusztusban további négy új dalt rögzítettek. Az Angels Fall First album megjelenése előtt boltokba került a "The Carpenter" kislemez, amely a hivatalos finn listán a 8. helyig kúszott fel. A nagylemez novemberben látott napvilágot, és a 31. helyezést érte el a finn lemezlistán.
A zenekar első koncertjét 1997 szilveszterén Kiteeben adta. Ezt követően csupán hét további fellépésen játszottak a tél folyamán, mert Emppu és Jukka bevonult a hadseregbe, Tarját pedig lefoglalták tanulmányai. Eközben a Spinefarm az eredeti két lemez helyett háromra terjesztette ki a szerződést.
Az első videóklip ("The Carpenter") forgatása 1998 áprilisában kezdődött; ezt május elején a finn "Jyrki" című tévéműsor tűzte először műsorára, mely a hónap végén egy Tuomasszal és Tarjával készített interjút is leközölt. Az ezt követő nyáron a basszusgitáros Sami Vänskä is csatlakozott a csapathoz; vele együtt kezdődtek az új album dalainak próbái. Augusztus elején a zenekar ismét stúdióba vonult, október végére pedig be is fejeződtek a felvételek. November 13-án újabb Kitee-beli koncertre került sor; itt készült a "Sacrament of Wilderness" videó. A megegyező című kislemez november 26-án, az Oceanborn névre keresztelt új album pedig december 7-én jelent meg.
A lemez sikere mindekit meglepett. Az Oceanborn a finn lemezlista 5. helyére tornázta fel magát, a "Sacrament of Wilderness" dal pedig hetekig vezette a slágerlistát. Az 1999-es év telét a Nightwish turnézással töltötte, de játszottak ismét a tévében is. A következő év tavaszán az Oceanborn a külföldi lemezboltok polcaira is felkerült. Májustól a banda ismét két és fél hónapos koncertkörútra indult, melynek során az összes jelentős finn rockfesztiválon megfordultak. Ezzel egy időben rögzítették a "Sleeping Sun" című dalt, melyet a németországi napfogyatkozás ihletett. Augusztusban meg is jelent Németországban a kislemez, mely e dal mellett a "Walking In The Air", "Swanheart" és az "Angels Fall First" című szerzeményeket tartalmazta. Csupán Németországban 15.000 darab fogyott belőle egy hónap leforgása alatt. Ugyanekkor a zenekar megtudta, hogy az Oceanborn album és a "Sacrament of Wilderness" daluk bearanyozódott, és vár rájuk egy 26 állomást érintő európai turné a német Rage társaságában.
A 2000. év elején a Nightwish újra stúdióba vonult, hogy immáron harmadik albumuk munkálatait készítsék elő. A felvételeket egy rövid, de fontos kitérő szakította meg: a zenekar "Sleepwalker" című dalával részt vett az Eurovíziós Dalfesztivál finn képviselőinek versenyén. Bár végül hivatalosan a második helyre szorultak, a közönségszavazatok alapján elsöprő győzelmet arattak. Májusban megjelent az új album, mely a Wishmaster címet viselte, s útjára indult a Wishmaster Tour, ezúttal is - mint mindig - Kiteeből, a Nightwish szülővárosából. Ezen a koncerten vehette át a banda az
Oceanborn, a "Sacrament of Wilderness", a "Walking in the Air" és a "Sleeping Sun" kiadványok után járó aranylemezeket. A Wishmaster rögtön a finn lemezeladási lista élén nyitott, s három héten át őrizte előkelő pozícióját. Ezalatt az idő alatt az aranylemez státuszt is sikerült elérnie. A Wishmaster mind a rajongók, mind a kritikusok körében kedvező fogadtatásra lelt; a német Rock Hard magazin júniusi számában a hónap korongjává választotta, megelőzvén ezzel a már régóta várt új Bon Jovi és Iron Maiden albumokat. A lemez a német eladási listán a 21., míg Franciaországban a 66. helyen debütált. A Wishmaster World Tour pedig Kittee és a nagyobb finn fesztiválok után 2000 júliusában Dél-Amerikában folytatódott. A Brazíliát, Chilét, Argentínát, Panamát és Mexikót érintő 3 hetes körút óriási élményt jelentett a zenekar számára. A koncertsorozat a Wacken Open Air és Biebop Metal fesztiválon dübörgött tovább, majd egy újabb európai körút következett a Sinergy és az Eternal Tears Of Sorrow társaságában. Novemberben a Nightwish Kanada felé vette az irányt, ahol két koncertet adtak. A következő kihívás a zenekar életében egy teljes koncertanyagot tartalmazó live DVD és VHS - valamint a hozzá kapcsolódó, csak Finnországban forgalmazott, korlátozott példányszámú CD - elkészítése volt. A kiadvány a 2000. december 29-ei tamperei show-t örökíti meg. Ezen a fellépésen vehette át a Nightwish a Wishmaster albumért járó platina- és a "Deep Silent Complete single-ért járó aranylemezt. A DVD és a VHS szerte a világon 2001 nyarán került a boltokba.
2001 márciusát újra a stúdióban töltötte a zenekar, ahol ezúttal egy Gary Moore klasszikus, az "Over The Hills and Far Away" című dal Nightwish-féle feldolgozását játszották fel, két új szerzeménnyel és az Angels Fall First albumon található "Astral Romance" felújított változatával egyetemben. Finnországban 2001 júniusában jelent meg ez az EP, mely a német Drakkar által forgalmazott kiadásban további 6 koncertfelvételt is tartalmazott. A zenekar eközben meghosszabbította szerződését a Spinefarm Recordsnál még egy nagylemez erejéig, melynek megjelenését következő nyárra tervezték. Még ezen a nyáron elkészült az addigra platina státuszt elérő "Over The Hills and Far Away" című dal videóklipje is. A 2001-es turné a finn Nivalában zárult, de ekkorra a banda közel állt a felbomláshoz. Tuomas Lappföldre indult, hogy vándorlásai közepette rendezze gondolatait: a Nightwish fennmaradása érdekében változásokra volt szükség. Saját bevallása szerint Tuomas a tagok között régóta húzódó ellentétek miatt a zenekar feloszlatása mellett döntött.
Szerencsére ez mégsem következett be. Ennek ellenére sok változás ment végbe a zenekar életében. Sami Vänskä, aki az Oceanborn óta játszott a Nightwishben, többé nem volt a banda tagja. Helyére - az új lemez felvételei és az azt követő turné idejére - a Tarotból és Sinergyből ismert Marco Hietala lépett. A koncertek szervezéséért ezentúl a King Foo Entertainment vállalt felelőséget, míg a menedzser szerepét ekkortól a régi barát és munkatárs Ewo Rytkönen töltötte be. Az "új kezdet" méltó ünnepléseként 2001 novemberében megnyílt a Nightwish Bolt a zenekar hivatalos honlapján. Az új album, a Century Child munkálatai 2002 januárjában kezdődtek.
Az új év - a korábbi nehéz napok után - kellemes hírekkel köszöntött be. Mind a zenekar, mind az egyes tagok előkelő helyezéseket értek el a hazai és külföldi magazinok olvasói által összeállított éves listákon. Úgy tűnt, a rajongók a változások után is teljes bizalmat szavaztak a bandának. Az "Ever Dream" című kislemez, az új album beharangozója, 2 nap alatt aranyozódott be Finnországban. Ezzel párhuzamosan a Nightwish hivatalosan is bejelentette, hogy a Century Child világturné után hosszabb szünetet tart majd, mialatt Tarja befejezheti németországi tanulmányait. Ez a hír számos találgatásra adott okot a rajongók körében hiszen először Sami hagyta el a zenekart, most pedig egy egész éves szünetre készültek ...
A Century Child album 2002 májusában jelent meg Finnországban, s rögtön példa nélküli eladási rekordot állított fel: mindössze 2 óra leforgása alatt elérte az aranylemez státuszt! Két hét múlva már platinalemez lett (30.000 eladott példány), és továbbra is szépen fogyott - miközben a zenekar életében először egyszerre foglalhatta el a vezető pozíciót a kis- és nagylemezek listáján. Külföldön hasonló sikereket ért el az album: Németországban az 5., Ausztriában a 15. helyen nyitott - mindezidáig ezek voltak a zenekar legmagasabb helyezései a nemzetközi eladási listákon. Júliusban újra Dél-Amerikában játszott az együttes, ahol szinte minden állomáson teltház fogadta őket; Brazíliában a Century Child első kiadása egy nap alatt elfogyott. Az ezt követő sikeres európai lemezbemutató turné a koncertszervező cégek figyelmét is felkeltette. Több európai fellépést az internet élőben is közvetített, ami gyakran fennakadásokat okozott a szolgáltatók szerverein - egy alkalommal közel 10.000 rajongó próbálta egyidőben figyelemmel követni a koncertet. Otthon ezalatt 59.000 darab fogyott a Century Child albumból, mely elképesztő számmal ez vált a 2002-es esztendő második legkeresettebb zenei kiadványává Finnországban. És végre először a szomszédos Svédországba is eljutott a banda november 16-án.
A szünet 2002 végén vette kezdetét, de az elkövetkezendő hónapok egyik tag számára sem teltek semmittevéssel. Jukka a Sethianban és a Bitch Drivenben dolbolt, Tuomas játszott a Sethiannal, a For My Painnel és a Timo Rautiainen & Trio Niskalaukaus zenekarral, Emppu az Altarban, Marco pedig a Tarotban nyűtte a húrokat. Még le sem telt az egy év, s a fiúk újra az úton voltak ...
A 2003-as esztendő ismét jól indult: a rajongók újra kitüntették szavazataikkal a Nightwisht megannyi európai magazin listáján, miközben a stúdió már várta a zenekart, hogy a következő évre tervezett új album felvételeit megkezdhessék.
A családi események is sok örömre adtak okot, hiszen 2003. március 11-én megszületett Jukka és Satu kislánya, Luna. A 60.000 példányban elkelt Century Child albumért pedig első dupla-platina lemezét vehette át a csapat. Az év során szinte folyamatosan külföldön játszott a zenekar, a sort mindössze egyetlen hazai koncert törte meg. Eközben elkezdődtek az End of Innocence címre keresztelt dokumentum DVD összeállításának munkálatai, melynek megjelenését többször is el kellett halasztani a feldolgozásra váró óriási mennyiségű anyag miatt. Májusban Tarja közzé tette, hogy néhány hónapja titokban házasságot kötött, s tervei szerint hamarosan visszaköltözik Finnországba. Az End of Innocence DVD végül október 6-án került a boltokba, miközben a csapat már legújabb lemezén dolgozott a stúdióban. Úgy tűnt, készülő ötödik albumuk, a Once a legfontosabb kiadvány lesz a Nightwish életében. Az év végén a finn köztársasági elnök, Tarja Halonen, a Nightwish érdemeinek elismeréseképpen meghívta Tarja Turunent és férjét, Marcelo Cabulit az elnöki palotában tartott hagyományos Függetlenség Napi ünnepségre. Az estélyen Tarját választották meg a legszebben öltözött vendégnek. Karácsony előtt a zenekar árverésre bocsátotta azt a képet, mely 2003-as turné során a színpad hátteréül szolgált, majd az összeget teljes egészégben jótékonysági célokra fordította. Az összegyűlt pénzt Tarja Turunen adta át a riistinai Parikanniemi Gyermekotthonnak.
Mind a rajongók, mind a zenekar különleges elvárásokkal nézett a 2004-es esztendő elébe. A kimerítő stúdiómunka nem csak fizikailag, de lelkileg is megviselte a tagokat. A felvételek a londoni Phoenix stúdióban készültek - pontosan azon a helyszínen és azzal a zenekarral (The Academy of St.Martins in the Field), ahol és akik közreműködésével Howard Shore a Gyűrűk Ura mozifilm trilógia zenéjét szerezte. A nagyzenekari- és kórusbetéteket Pip Williams hangszerelte, aki korábban a Status Quo és Uriah Heep lemezek készítésében is részt vett. Remek élmények, szép remények!
Az új albumról először a "Nemo" kislemez jelent meg, melyhez egy óriási költségvetésű videó is készült Antti Jokinen rendezésében, aki ezt megelőzően Shania Twainnel és Eminemmel forgatott. Az új lemezhez új szerződés is társult: az anyag a Nuclear Blast kiadó védőszárnyai alatt jelent meg.
Finnországban azonban továbbra is a Spinefarm felelős a Nightwish szerzeményeinek terjesztéséért. Németországban a Nuclear Blast kiadó jelentős összeget fordított a Once album reklámozására - a Nightwish és az új album borítójának képe feltűnt a metrón, buszokon, utcákon, magazinok oldalain és a tévécsatornák hirdetéseiben - így talán mára nincs is olyan német ember, aki ne ismerné a Nightwish nevét. A Once album és a "Nemo" kislemez már megjelenése napján aranylemez lett Finnországban. A zenekar pedig újra világkörüli koncertkörútra indult, melynek során 2005 végéig több kontinens 150 országában lépnek színpadra. A Nightwish eddigi fennállásának leghosszabb turnéja elé néz ...