"Nemo", в общей сложности десятый сингл группы, стал первым синглом в поддержку альбома Once. Он вышел 19 апреля 2004 года. В стандартную версию сингла, помимо заглавной песни, вошел ее оркестровый вариант (с вокалом), а так же другая композиция с альбома, "Planet Hell", и бонус-треки "White Night Fantasy" и "Live To Tell The Tale". Именно этот сингл стал первым синглом группы, выпущенным немецким лейблом Nuclear Blast. Лейбл оказал синглу мощную поддержку, выпустив четыре разных его версии и множество промо-материала, от маек до плакатов.
Сингл получил золотой статус в Финляндии всего за неделю, а еще через неделю получил и платиновый статус, будучи проданным тиражом более 15000 копий. Он возглавил чарты в Финляндии, Венгрии, Бразилии, вошел в десятку в чартах Греции, Норвегии, Португалии, Германии, Словакии, получил восьмое место в рок-чартах Великобритании.
В поддержку к синглу известным режиссером Antti Jokinen-ом был снят видеоклип. Йокинен работал с такими известными исполнителями, как Шанайя Твейн, Селин Дион и Eminem, а впоследствии стал режиссером DVD "End Of An Era". Сценарий клипа написали Туомас и Теро Киннунен, однако Йокинен поправил несколько моментов. Клип был снят в готической стилистике, в то время находящейся на пике популярности, и очень понравился публике. Например, в чартах бразильского MTV "Nemo" получил первое место. Нельзя так же не заметить, что это был первый клип Nightwish, который был показан на российском MTV, и именно благодаря нему группу широко узнали в нашей стране.
"Nemo" вошла в саундтрек к фильму The Cave, и существует вторая версия видеоклипа, включающая кадры из этого фильма.