2001—2003

Nightwish запісалі відэа для DVD (поўны канцэртнік) і VHS з абрэзаным жывым канцэртам (толькі для Фінляндыі), які праходзіў у Тампере 29 снежня 2000 года. У запісы прымалі ўдзел Тоні Какко (en) з групы Sonata Arctica і Тапіё Вільска. Матэрыял быў выпушчаны ў красавіку 2001 года ў Фінляндыі, а на працягу года і ва ўсім міры. DVD выйшаў пад назовам «From Wishes to Eternity». У канцы паказу Nightwish атрымалі плацінавы дыск за «Wishmaster» і залаты дыск за «Deep Silent Complete».

У сакавіку 2001 года Nightwish зноў памкнуліся ў студыю, каб запісаць сваю версію класічнай кампазіцыі Гэры Мура «Over the Hills and Far Away» з двума новымі песнямі і рымэйкам з альбома «Angels Fall First» песні «Astral Romance». У Фінляндыі ён з'явіўся ў чэрвені 2001 года.

Нямецкая версія «Over the Hills and Far Away» уключае шэсць жывых трэков у дадатак да чатырох нявыпушчаных песень. Неўзабаве пасля гэтага групу пакінуў бас-гітарыст Самі Вянскя і замест яго прыйшоў Марка Хіетала, пакінуўшы каманду Sinergy. Таксама Марка з'яўляецца вакалістам і бас-гітарыстам фінскай металічнай групы Tarot. Новы бас-гітарыст не толькі гуляе на сваёй прыладзе, але і спявае моцным высокім вакалам. Трэба заўважыць, што манера спеву Марка Хіетала ў песнях Nightwish трохі адрозніваецца ад яго манеры спеву ў групе Tarot.

У 2002 годзе група выпусціла альбом «Century Child» і сінглы «Ever Dream» і «Bless the Child». Асноўным адрозненнем ад папярэдняга альбома з'яўляецца тое, што ў запісы шматлікіх песень прыняў удзел фінскі аркестр, набліжаючы яго да класічнай музыкі. Пасля першага кліпа «Bless The Child» быў запісаны другі «End of All Hope». У ім выкарыстоўваліся ўрыўкі з фінскага фільма «Kohtalon Kirja» (финск. «Кніга Лёсу»).

У 2003 годзе Nightwish выпусцілі свой другі DVD «End of Innocence». Таксама ўлетку 2003 года Тар'я выйшла замуж. Пасля гэтага паўстаў слых аб тым, што група можа распасціся, але, нягледзячы на гэта, група працягнула выступаць і ў наступным годзе выпусціла новы альбом.

У канцы жніўня 2001 года ў рамках тура група прыехала ў Расею. Nightwish далі два канцэрту, адзін у Санкт-Пецярбурзе, на малой арэне ДС «Юбілейны», другі ў Маскве, у ДК Гарбунова.