-------------------------------------- Apparition d'orchestrations et nouveau bassiste (2001-2003)-----------------------
Marco Hietala, remplaçant du bassiste Sami Vänskä.
En 2001, Nightwish enregistre une reprise de Over the Hills and Far Away de Gary Moore. Le morceau sort dans l'EP Over the Hills and Far Away avec deux nouvelles chansons et un "remake" d'Astral Romance, une chanson du premier album ; Tony Kakko (de Sonata Arctica) et de nouveau Tapio Wilska participent à l'enregistrement. Ce disque obtient le statut de disque d'or en Finlande.Le groupe sort aussi VHS, DVD et CD de l'enregistrement d'un concert à Tampere le 29 décembre 2000, intitulé From Wishes to Eternity.
Peu après, Tuomas trouve que Sami Vänskä n'est plus assez motivé et lui propose de quitter le groupe. Il est remplacé par Marco Hietala, qui conserve sa place dans le groupe Tarot, qu'il a formé avec son frère (il quitte cependant son autre groupe, Sinergy Le bassiste, en plus de jouer de son instrument, s'occupe des ch½urs masculins au sein de Nightwish. Tuomas a déclaré par la suite que lui et Sami restaient en contac, afin de mettre fin aux rumeurs selon lesquelles ils ne s'étaient plus reparlé depuis.
En 2002, Nightwish sort Century Child, accompagné des singles Ever Dream et Bless the Child. La principale différence avec les autres albums est la participation d'un orchestre sur Bless the Child,Ever Dream, Feel For You et Beauty of the Beast, rapprochant les morceaux de la musique classique. The Phantom of the Opera est la version du groupe du fameux morceau d'Andrew Lloyd Webber de la comédie musicale du même nom. Century Child est certifié disque d'or seulement deux heures après sa sortie, et platine deux semaines après; un record dans les charts d'albums finlandais. Après le clip de Bless the Child, un clip est enregistré pour End of All Hope mais sans le support d'un single. Le clip contient des scènes du film finlandais Kohtalon kirja.
En 2003, Nightwish sort un second DVD, intitulé End Of Innocence qui raconte l'histoire du groupe à travers les dires de Tuomas Holopainen et Jukka Nevalainen pendant deux heures. Le documentaire inclut également quelques instants de concerts.
Tarja Turunen se marie durant l'été 2003, faisant naître des rumeurs sur la dissolution prochaine du groupe. Pourtant, le groupe continue de jouer en concert pendant encore un an et sort un autre album.