"Nightwish" grubunun kurulmasına Temmuz 1996'da karar verdi.O zamanlar Holopainen,kendine ait şarkı sözlerini yazabileceği ve kalvye çalabileceği bir gruba sahip olmak istiyordu.Bu da Nightwish'in kamp ateşi etrafında doğmasıydı.<br />
Müzik okulundan arkadaşı [[Emppu Vuorinen]] ve sınıf arkadaşı [[Tarja Turunen]] başta olmak üzere dostlarıyla konuyu ele alan sanatçının kafasında bir isim yoktu ancak fikir şekillenmişti. Kurulacak grup sadece [[gitar]], [[flüt]], vokal ve [[klavye]]den oluşacan bir [[akustik müzik]] grubu olacaktı. Grubun ilk üç şarkısı Kasım ve Aralık [[1996]]'da kaydedildi ve ilk demolarını çıkardılar. Grup şarkılara davulun nasıl eklenebileceğini merak etti ve [[Jukka Nevalainen]] gruba dahil oldu. Daha sonra da akustik gitar yerine elektro gitar geldi. Bu sayede Nightwish akustik müzik yapmaktan çıkıp [[metal müzik]] yapmaya başladı. Birkaç haftalık çalışmadan sonra grup Nisan 1997'de stüdyoya girdi ve "[[Angels Fall First]]" albümünün kısıtlı sayıda üretilen versiyonu ortaya çıkmış oldu. 1998 yılında basçı [[Sami Vänskä]] gruba dahil oldu. Aynı yıl Nightwish ikinci albümleri "[[Oceanborn]]" u piyasaya sürdü. 1999'da Holopainen ve diğer [[Embraze]], [[Eternal Tears of Sorrow]], [[Charon]] ve [[Reflexion]] gibi metal gruplarının üyeleri [[For my Pain...]] gibi bir süpergrup projesini hayata geçirdiler.Bununla beraber tüm grup üyelerinin kendi gruplarıyla meşgul olmasıyla proje geleceğe ertelendi.<br />
İkinci albüm "[[Oceanborn]]"un çıkışını "[[Wishmaster]]" izledi.[[2000]] yılında çıkan ''[[Wishmater]]'' albümündeki tüm şarkıları Holopainen yazmıştır.[[Nightwish]]'in üçüncü albümü olan ''Wishmaster'' geçen albüme oranla daha fazla satmıştır.<br />
