2004—2005

Новы альбом, названы «Once», выйшаў 7 чэрвеня 2004 года, пасля сінгла «Nemo» (лат. ніхто) з гэтага альбома. У запісы 9 з 11 песень альбома прыняў удзел аркестр. У адрозненне ад «Century Child», у запісы «Once» прымаў удзел не фінскі аркестр, а Лонданскі сесійны аркестр, які таксама ўдзельнічаў у запісы саўндтрэка да «Уладару Кольцаў». Гэта таксама другі альбом з песняй цалкам на фінскай мове «Kuolema Tekee Taiteilijan». У запісы песні «Creek Mary’s Blood» прыняў удзел індзеец племя Лакота Джон «Two-Hawks». Ён спявае на роднай мове і гуляе на флейце.

Былі выпушчаныя наступныя сінглы: «Wish I Had an Angel» (саундтрэк да фільма «Alone in the Dark»), «Kuolema Tekee Taiteilijan» (выходзіць толькі ў Фінляндыі) і «The Siren». Новы альбом быў добра сустрэты крытыкамі, якія параўноўвалі яго з «Oceanborn».

Поспех альбома дазволіў групе адправіцца ў сусветны тур «Once», у тым ліку ў тыя краіны, у якіх яны яшчэ ніколі не выступалі. Яны прынялі ўдзел у адкрыцці Сусветнага Чэмпіянату па Атлетыцы 2005 года, які праходзіў у Хельсінкі, выступіўшы з песняй «Nemo».

У верасні 2005 года выйшаў зборнік «Highest Hopes», які складаецца з песень, сабраных з усёй дыскаграфіі групы. Ён таксама ўключае кавер на кампазіцыю «High Hopes» групы Pink Floyd. Акрамя гэтага быў таксама зроблены рымейк на «Sleeping Sun», які таксама выйшаў як сінгл. Для яго быў зняты новы кліп са сярэднявечнай бітвай.