October 21, 2005, was arguably the most shocking date in the history of Finnish heavy metal. Nightwish’s performance for 11,500 fans at Helsinki’s Hartwall Arena, was the culmination of the symphonic power-metal quintet’s tour for 2004’s million-selling Once. But right after the show, the band fired frontwoman Tarja Turunen, whose dark-haired, Gothic beauty and classically trained vocals had defined Nightwish’s image. The decision was subsequently announced via an open letter that called Turunen a money-oriented diva who wasn’t interested in rehearsals. She, however, claimed to have been completely blind-sided by it all.

Nearly three years later, the squabbling parties have moved on. Turunen’s pensive solo debut, My Winter Storm, has been certified platinum in Finland (which means 30,000 copies sold), and is approaching the 100,000 mark in Germany. Meanwhile, in 2007 Nightwish teamed up with Anette Olzon, a charming Swede who sounds closer to Heart’s Nancy Wilson than her operatic predecessor. However, according to songwriter-keyboardist Tuomas Holopainen, the overall direction for the band’s latest CD, a 75-minute epic on Nuclear Blast Records entitled Dark Passion Play, wasn’t affected by Olzon’s arrival.

“Many people seem to think this is a completely new start for the band,” says the 31-year-old Kitee native, calling from the Nuclear Blast headquarters in Donzdorf, Germany. “But I think this album is a natural sequel to Once. All that’s changed is the female vocalist. When I listen to the album, I feel it’s the hardest, saddest, and most melancholy thing we’ve done so far.”

Still, compared to the Tchaikovsky–meets–John Williams bombast of its early material, Nightwish has shown some poppier tendencies in recent years. That’s true of the addictive, Rammstein-like groove of Once’s “Wish I Had an Angel” and the soaring chorus of the second single off Dark Passion Play, “Amaranth”. That’s counterbalanced by the 14-minute theatrical madness of “The Poet and the Pendulum”.

Nightwish isn’t afraid to spend big in its pursuit of success: the 10-month recording process for Dark Passion Play cost close to $775,000 including fees for sessions with choirs and orchestras at London’s Abbey Road Studios. And while simpler, more abrasive metal is generally more popular in North America, a buzz is building around Nightwish’s ultra-European pomp and glory, as reflected by its already-sold-out Vancouver show.

Looking back now, Holopainen can view the search for Turunen’s replacement with wry humour: “Almost every single female vocalist in a contemporary metal band was rumoured to be our new lead singer. It was in the tabloids all the time, especially in Finland, that Liv Kristine of Leaves’ Eyes would be the new singer. At some point, it was even Amy Lee of Evanescence or Vibeke Stene of Tristania. It got totally out of hand and became a public soap opera.”

Nightwish plays the Croatian Cultural Centre on Tuesday (May 20).