Nightwish
Lịch sử hoạt động > Thành công trên bảng xếp hạng với Once và biến cố Tarja (2004)

Bài chi tiết: Once Upon a Tour
Album mới, Once được phát hành ngày 7 tháng 7 năm 2004, cùng với single quảng bá, "Nemo" (tiếng Latin: "Không một ai"). Single đứng đầu bảng xếp hạng Phần Lan và Hungary, và lọt vào bảng xếp hạng của sáu nước khác. "Nemo", vì thế, được xem là single thành công nhất của nhóm từ trước đến nay. Với Once, Nightwish bắt đầu soạn phiên bản giao hưởng của một số bài hát trong album. Các bài hát gồm có "Nemo", "Ghost Love Score", "Kuolema Tekee Taiteilijan" và "Creek Mary's Blood".
Once sử dụng một dàn nhạc giao hưởng trọn vẹn trong chín trên tổng số mười một bài hát. Không như Century Child, Nightwish quyết định lựa chọn một dàn nhạc giao hưởng ngoài Phần Lan, và dàn nhạc giao hưởng London Philharmonic Orchestra được chọn. Đây cũng là album thứ hai có một bài hát toàn bộ là tiếng Phần Lan, "Kuolema Tekee Taiteilijan" ("Tử thần tạo nên một nghệ sĩ", tiếng Anh: "Death Makes an Artist"). Once giành được ba đĩa bạch kim ở Phần Lan, một đĩa bạch kim khác ở Đức, và đĩa vàng ở sáu nước khác, album này cũng đạt vị trí số một tại bảng xếp hạng âm nhạc Hy Lạp, Na Uy và bảng xếp hạng album của Đức, nằm trong top 10 của bảng xếp hạng Pháp, Hungary và Thụy Điển. Các đĩa đơn sau đó là: "Wish I Had an Angel" (là soundtrack của phim Alone in the Dark), "Kuolema Tekee Taiteilijan" (chỉ phát hành tại Phần Lan và Nhật Bản) và "The Siren". Bên cạnh thành công về mặt thương mại, Once cũng được đón nhận bởi nhiều nhà phê bình, với nhiều nhận xét tích cực và so sánh với Oceanborn.
Thành công của album đưa ban nhạc lưu diễn trong tour Once World Tour đến nhiều nước trên thế giới mà họ chưa bao giờ đến. Nightwish được vinh dự biểu diễn mở màn Giải Vô địch điền kinh thế giới lần thứ 10 năm 2005, tổ chức tại Helsinki. Một album "best of", Highest Hopes, cũng được phát hành vào tháng 9 năm 2005. Album tổng hợp này bao gồm một bản live cover "High Hopes" (từ album The Division Bell của Pink Floyd) (sample). Bên cạnh High Hopes, một bản làm lại của "Sleeping Sun" (từ Oceanborn) cũng nằm trong album, và được phát hành như một đĩa đơn. Một đoạn video mới cho "Sleeping Sun" đã được tiết lộ, với một trận chiến thời Trung cổ, và có thể tìm thấy trên đĩa đơn phiên bản tiếng Đức và một DVD riêng biệt phát hành bởi Spinefarm.
Sau khi thu âm live ở Hartwall Arena (Helsinki) vào ngày 21 tháng 10 năm 2005, cho DVD End of an Era (phát hành tháng 6 năm 2006), bốn thành viên còn lại quyết định rằng sẽ là tốt nhất cho Nightwish nếu tiếp tục mà không có Tarja Turunen, một cảm nhận mà họ thể hiện qua một bức thư ngỏ được gửi tới Turunen từ Holopainen sau buổi biểu diễn, và sau đó được đăng trên website của ban nhạc. Bức thư do Holopainen viết nhưng được ký tên bởi ba thành viên còn lại. Trong bức thư, lý do chính được đưa ra cho việc Tarja bị khai trừ khỏi là vì ban nhạc cảm thấy rằng cả người chồng Marcelo Cabuli (một doanh nhân người Argentina) và niềm yêu thích thương mại đã thay đổi thái độ của cô đối với toàn bộ ban nhạc.
Turunen phản ứng lại động thái này hai lần, trong hai buổi họp báo ở Phần Lan và Đức, nói rằng việc bị khai trừ là một cú sốc lớn với mình, thêm nữa, cô hoàn toàn không biết gì cho tới khi nhận được lá thư. Cô cảm thấy rằng những lời lẽ nhắm vào chồng mình là không có cơ sở, và việc tuyên bố công khai là "vô cùng điên rồ và tàn nhẫn". Cô cũng bày tỏ quan điểm của mình trong một bức thư ngỏ khác đăng tải trên website của riêng mình, và thông qua nhiều bài phỏng vấn trên báo, tạp chí và truyền hình.