Идеята за създаването на Nightwish се заражда през лятото на 1996-а година край един лагерен огън. Младият Tuomas Holopainen и приятелите му Tarja Turunen и Emppu Vuorinen, забавлявайки се, създават няколко песни. Музиката е комбинация от акустични китари, ефирни синтезаторни мелодии и прекрасният глас на Tarja (която по това време учи оперно пеене в академията Sibelius). Това, което започва като обикновено хоби, скоро се превръща в сериозно занимание за начинаещите музиканти. В края на годината тримата записват едноименно демо в студио Kitee Huvikeskus, което Tuomas разпраща по метъл магазини и финландски лейбъли. Лентата не достига до широка публика, а повечето лейбъли дават добри отзиви, но така и не предлагат договор на групата.
В началото на 97-ма Nightwish отново влизат в студиото, където записват седем нови песни. Emppu изпълнява акустични, електрически и бас китари, Tuomas свири клавир и участва с вокали в някои парчета. Новото попълнение в състава е барабанистът Jukka Nevalainen, приятел на Emppu. Новото демо привлича вниманието на Spinefarm Records, които предлагат на Nightwish договор за два албума. Записани са още няколко песни, които заедно с готовите вече, влизат в дебютния студиен албум на групата - “Angels Fall First”. Музиката представлява атмосферичен метъл с готик и пауър елементи - стил, който Nightwish тепърва ще развиват и обогатяват. През ноември е издаден сингълът “The Carpenter”, а самият албум излиза скоро след това и попада на 31-во по продажби във Финландия.
Бандата провежда първия си концерт в Kitee на 31-ви декември 1997. През зимата изнасят още седем концерта, след което Jukka и Emppu отиват в казармата, а Tarja се заема с уроците си. През април, 98-ма, е заснет първият видеоклип на групата - по песента “The Carpenter”. Към Nightwish се присъединява басистът Sami Vanska. В края на годината групата започва да записва песните за новия си албум и през ноември излиза сингълът “Sacrament of Wilderness”. Вторият дългосвирещ албум на Nightwish, озаглавен “Oceanborn”, излиза на 7-ми декември и печели голямо признание за групата, достигайки до пета позиция във финландските класации. През пролетта на 99-а албумът е издаден в цяла Европа, след което бандата поема на голямо турне, свирейки на всички големи европейски фестивали в подкрепа на новия си албум. Nightwish влизат за кратко в студио, за да запишат сингъла “Sleeping Sun”, включващ освен едноименната песен (посветена на слънчевото затъмнение с.г.) и парчетата “Walking in the Air”, “Swanheart” и “Angels Fall First”. До края на годината Nightwish провеждат още 26 концерта съвместно с немските ветерани Rage.
В началото на 2000 г групата започва записите на третия си албум. Работата на петимата в студиото е прекъсната за кратко по време на музикалното състезание Eurovision, в което Nightwish заемат второ място, въпреки че получават най-много гласове от публиката. Албумът “Wishmaster” излиза през май и се задържа над три седмици на върха на финландските класации, като постига и платинен статут по продажби. Звученето е все така величествено и симфонично, макар и осезаемо по-тежко. Бандата за пръв път изнася концерти в Южна Америка и е посрещната с възторг от тамошните фенове. Турнето към “Wishmaster” продължава в Европа, където Nightwish са хедлайнери и свирят заедно със Sinergy и Eternal Tears Of Sorrow. На 29-и декември се състои един много специален концерт за групата във финландския град Tampere. Шоуто е записано и впоследствие издадено в DVD и VHS формат под заглавието “From Wishes To Eternity”. Финландските фенове получават и самостоятелно лайв-CD от въпросния гиг. През 2001-ва Nightwish записват EP-то “Over The Hills And Far Away”, съдържащо кавър на едноименната песен на Gary Moore, както и още две нови парчета. Немската версия на EP-то включва и шест песни от концерта в Tampere.
В края на годината Sami напуска състава и Tuomas довежда на негово място една легендарна фигура за финландския метъл - басистът и вокалист Marco Hietala (познат на феновете от Tarot и Sinergy). С него бандата влиза в студио Finnvox за четвъртия си дългосвирещ запис - “Century Child” (2002). Албумът се оказва най-експерименталната творба на Nightwish, в която композиторското майсторство на Tuomas намира израз в мрачни настроения и по-тежко отвсякога звучене. В някои парчета се включва като певец и Marco, а вокалите на Tarja са по-земни и не толкова оперни, но не по-малко красиви. В записите взимат участие градският оркестър и хор на Joensuu, придавайки допълнителна дълбочина и епичност на музиката. Квинтетът изнася редица концерти до началото на 2003-та, части от които са записани за обявеното биографично/концертно DVD “The End Of Innocence”. Nightwish взимат заслужена почивка т.г., но се очаква през 2004-та една от най-оригиналните и неподаващи се на стилови ограничения групи да зарадва феновете си с нов симфоничен шедьовър.