W roku 2000 grupa wydała kolejny album „Wishmaster”, poprzedzony startem w eliminacjach do Eurowizji (z utworem "Sleepwalker"), w których Nightwish zajęli drugie miejsce. Album osiągnął pierwsze miejsce na fińskiej liście przebojów, pozostając na nim przez trzy tygodnie; zyskał również status złotej płyty. Co więcej, „Wishmaster” został albumem miesiąca w niemieckim magazynie „Rock Hard” pomimo faktu ukazania się w tym samym czasie długo oczekiwanych produkcji Iron Maiden i Bon Jovi.
Piąty album Finów „Century Child” pojawił się w sklepach w roku 2002. W nagraniach wielu utworów z tego krążka jako tło wykorzystano orkiestrę. Płyta zyskała status złotej płyty zaledwie po dwóch godzinach od jej wydania, by po dwóch tygodniach stać się albumem platynowym.
W 2003 roku na rynku ukazało się DVD „End of Innocence” zawierające m.in. dokument o historii zespołu. Rok później wydany został szósty album studyjny „Once”. W dziewięciu z jedenastu utworów usłyszeć można podkłady w wykonaniu orkiestry London Session Orchestra, znanej m.in. z soundtracku trylogii "Władca Pierścieni". Wyniki sprzedaży: potrójna platyna w Finlandii, platyna w Niemczech, złota płyta w Szwecji; pierwsze miejsca na listach przebojów w Grecji, Norwegii, Niemczech i na Węgrzech.
W 2005 roku, zespół po raz pierwszy pojawił się w Polsce (Mystic Festiwal w Chorzowie). Po zakończeniu trwającej ponad półtora roku trasy koncertowej promującej „Once”, w październiku tego samego roku zespół ogłosił zakończenie współpracy z wieloletnią wokalistką Tarją Turunen.
Dopiero w maju 2007 roku fani poznali nazwisko nowej wokalistki, którą została Szwedka - Anette Olzon. We wrześniu 2007 w sprzedaży pojawił się album „Dark Passion Play”, wsparty intensywną promocją, między innymi singlami: „Eva”, „Amaranth” i „Bye Bye Beautiful” oraz wydanym w Finlandii „Erämaan Viimeinen” - fińską wersją utworu „Last of the Wilds”.
W lutym 2008 Nightwish odebrali w Niemczech nagrodę „ECHO” jako Grupa Roku w kategorii „rock/alternative (international)”. Miesiąc później grupa zdobyła z kolei 4 nagrody w kategoriach: „Album roku”, „Metalowy album roku”, „Zespół roku” oraz „Najlepiej sprzedający się album roku 2007” podczas gali „Emma” w Helsinkach. „Dark Passion Play” w samej Finlandii sprzedał się w liczbie 120 tys. egzemplarzy, co oznacza poczwórną platynę.
Tarja Turunen • Anette Olzon • Iron Maiden • Bon Jovi • Sonata Arctica • Nocturnal Rites • Vanishing Point • Baracuda • Angra • Kiko Loureiro • UnSun