In January 2004, the band was well on the album (Tarja’s vocals only had to be recorded) and Tuomas went in England to oversee the orchestral parts by the London Studio Orchestra: 52 musicians conducted by Pip Williams who worked on Lord of the Ring OST. Tuomas also contacted John Two-Hawks to ask him to play the flute and do some back vocals on the album. In January, Nightwish was given a gold disc for the DVD ‘From Wishes to Eternity” excellent sales.

In February, the band recorded a video clip for its first single called Nemo. While the Finns entered into negotiations with Spinefarm for their new album, German label Drakkar was dismissed and replaced by Nuclear Blast.

Tarja gave lectures and, in May, she flew to South America to give a few concerts as part of her studies in Karlsruhe University. Right after that, Nightwish announced a special concert on May 22nd 2004 in Kitee… The album Once was announced for June 7th 2004.

With the new album, Nightwish changed their contract and its release is dealt by Nuclear Blast, even if Spinefarm stays in charge of the band’s promotion in Finland. The German record company realized a very expensive marketing plan for Once, in Germany especially. Images with Nightwish and Once were broadcast on every TV channel, in the subway, buses and streets, and in the press. Every German would now know Nightwish.
Once became Gold Record in Finland the day it was released, just like the single “Nemo”. Nightwish was then ready to begin a world tour with more than 130 dates, on all continents. It started in May 2004 and lasted until October 2005 and was the longest tour the band had ever made. Nightwish played in countries they had never been to before: Japan, Australia, Colombia, Equator, Poland, Slovenia, Portugal, Danemark and Greece. Months after months, fans were more and more to attend their concert which made of this “Once Upon a Tour” a true success.

The second single Wish I Had An Angel” was released in fall 2004. The video was directed by Uwe Boll who also directed the movie “Alone in the Dark” whose soundtrack contains the song. This single was also a big surprise and boosted the sale of Once.

In August, Nightwish flew to the United States of America where they received a warm welcome. They then chose to plan an even bigger tour for 2005. Then, the band went straight to Europe then to South America in fall 2004, and they eventually played a few isolated concerts in December, before taking a one month break in January 2005.