Roku 1996 se již klávesákovi a skladateli Tuomasu Holopainenovi nechtělo podílet na projektech jiných kapel a proto oslovil své přátele zpěvačku Tarju Turunen a kytaristu Emppu Vuorinena. Téhož roku nahráli tři akustické demo skladby, z nichž byla první pojmenovaná Nightwish. Tato píseň se dostala do podvědomí lidí natolik, že určila název skupiny.
Přibližně rok po založení kapely se na scéně objevil známý finský vydavatel label Spinefarm Records, který jim nabídl smlouvu. Nighwish na tuto výzvu odpověděli přibráním bubeníka Jukky Nevalainena, také vyměnili akustickou kytaru za elektrickou a po několik týdnů pilně cvičili. Plodem jejich úsilí bylo sedmero písní alba Angels Fall First, které se okamžitě umístilo na 31 pozici v žebříčku. Na konci roku 1997 odehráli svůj první koncert v milovaném Kitee.
Duben roku 1998 byl ve znamení natáčení prvního videa The Carpenter. Tou dobou se ke skupině připojil basák Sami Vänskä a jejich spolupráce dala vzniknout úspěšnému albu oceanborn. Jeho úspěch překročil jejich všechny očekávání, v prodejnosti se vyšvihl až na pátou příčku. Singl Sacrament of Wilderness se dokonce po několik týdnu držel na první příčce. Oceanborn se proto brzy dostal i za hranice Finska a odstartoval tak první evropské turné, a to hnedka 26 konzertů.
Začátek roku 2000 znamenal započetí prací na třetím albu. V květnu byl již Wishmaster dokončen a téměř okamžitě katapultován na první místo žebříčku. Německý magazín Rock Hard ho i přes silou konkurenci bez váhání nazval albem měsíce. Ihned po tomto úspěchu vyrazili na "Wishmaster World Tour", kterou odstartovali tradičně v Kitee a přes velké finské festivaly zamířili Jižní Ameriku a také Kanadu. Během turné se dočkali zasloužené odměny v podobě zlatých desek za album Oceanborn a singly Sacrament of Wilderness, Walking in the Air a Sleeping Sun.
Další projekt, na který zaměřili svojí pozornost byl živý koncertní záznam na DVD, VHS a pro finské fanoušky limitovaná edice živě nahraného alba. Záznam je zakončen předáváním platinové desky za Wishmastera a zlaté za singl Deep Silent Complete. Poté následovala další dvě alba - From Wishes To Eternity (koncertní záznam spojený s DVD) a "minialbum" Over The Hills And Far Away - vydan roku 2001.
Kvůli dlouhotrvajícím neshodám nakonec došlo k nevyhnutelnému a kapelu opustil Sami Vänskä. Jeho místo pro připravované album a následné turné zaplnil Marco Hietala, známí s předešlého působení v kapelách Tarot a Sinergy. V květnu 2002 spatřilo světlo světa veleúspěšné album Century Child, jenž již po dvou týdnech získalo platinovou desku. Díky němu se také skupině poprvé podařilo obsadit první příčky finských žebříčků singlů i alb. Podobně kladného přijetí se albu dostalo i zahraničí. Následné turné odstartovali v červenci v Jižní Americe a téměř všechny představení byli plně vyprodané..
Rok 2004 byl považován za důležitý mezník kapely a dychtivě očekávané album Once bylo provázeno masivní mediální kampaní. Společně se singlem Nemo se fanoušci dočkali velkorozpočtového videoklipu. Samotné album získalo zlatou desku hnedka v den vydání a jak se u Nightwishů stalo tradicí, hned v květnu vyrazili na turné. Za téměř rok a půl koncertovali po celém světě na 150 vystoupení. Na podzim roku 2004 vyšel druhý singl, Wish I Had An Angel. Video k této písni natočil nechvalně proslulí Uwe Boll, režisér filmů "Alone In The Dark", kde tato píseň zazněla.
Po posledním koncertě turné 21.10.2005 v Hartwall Aréně došlo k vyhazovu Tarji. V otevřeném dopise bylo toto rozhodnutí odůvodněno jako její neztotožnitelný přístup ke skupině a i k fanouškům. Tarja se vydala na sólovou dráhu a zbytek kapely si dal pauzu. Po více jak roce volné místo po Tarje zaplnila Anette Olzon a mohlo se začít s pracemi na dalším albě Dark Passion Play. Tomu předcházela dvojice singlů. A to internetový singl "Eva", následovaná Amaranthem.
