翌98年には新たに正式なベーシストとしてサミ・ヴァンスケが加入し（それまではセッション・ミュージシャンを起用していた）5人編成となったバンドは、12月にセカンド・アルバム『オーシャンボーン』を発表、サウンド、楽曲、共に格段の進歩を見せたこの作品で一気にその人気を広げ、本国フィンランドではアルバム・チャート5位、今作収録の楽曲「サクラメント・オブ・ウィルダーネス」はシングル・チャート1位を記録。世界各国でもこの作品が発売され、ヨーロッパ、南米を中心に一気に世界規模のバンドへと成長していく。2000年にはサード『ウィッシュマスター』を発表、フィンランドではチャート1位を獲得、ドイツでもチャート21位に入るなど、その類まれなる音楽性は世界中のメタル・ファンから注目を集める存在となっていった。

その後、バンドにとって初のライヴ作品『フロム・ウィッシュ・トゥ・エタニティ』を2001年に発表、またミニ・アルバム『オーヴァー・ザ・ヒルズ・アンド・ファー・アウェイ』を発表するなど精力的に活動を続けていく。そして同年10月、サミ・ヴァンスケがバンドを脱退したことをうけ、新たにフィンランド初のプロフェッショナル・メタル・ミュージシャン、マルコ・ヒエタラを新たにベーシストとして迎え入れ、翌年2002年に4作目『センチュリー・チャイルド』を発表。マルコのヴォーカルやオーケストラをフィーチャーした今作は、本国フィンランドでは発売2時間でゴールド・ディスクを獲得、当然初登場1位を記録した今作は、ここ日本でも大きな注目を集めるようになっていく。今作に伴うツアーを終えた後、バンドは約１年の活動休止に突入、その間にユッカはSETHIANやBITCH DRIVEN、ツォーマスもSETHIANやFOR MY PAIN、エンプはALTER、マルコはTAROTといった別々のバンドで活動し、ターヤはドイツで声楽留学する。この活動休止中にツアーの模様やプライベート映像などを交えたドキュメンタリー作品『END OF INNOCENCE』（日本盤未発売）を2003年に発表。

そしてそれぞれの活動を経て再び活動を開始させた彼らは2004年に5作目『ワンス』を発表、本国フィンランドはもちろんのこと、ドイツ、ノルウェー、ハンガリー、ギリシャといった国々でもチャート1位を獲得し、メタルというジャンルを飛び越えた人気を博す巨大ロック・バンドとしての存在感を確立していく。日本でもこの作品で一気にブレイク、2005年3月には初の来日公演（アングラとのツアー）を大成功に終わらせている。2005年に開催された世界陸上選手権ヘルシンキ大会の開会式で同作収録曲「ニモ」をパフォーマンスし、より大きな舞台へと昇って行ったのだが、今作に伴うツアーが終了した2005年10月21日、バンドはターヤに対して公開書簡を手渡し、バンドからの脱退を言い渡すという事件が起こる。この事件はニュース番組や新聞などで大きく取り上げられ、フィンランドの大統領がコメントを発表するなど非常に大きな騒動となっていった。なお、この時のライヴの模様を収録した映像作品『エンド・オブ・アン・エラ』を2006年に発表している。

その後バンドはしばらく活動を休止しながら、新たなヴォーカリストのオーディションを行っていった。そして2007年5月24日、過去にミュージカルの主役を務めたり、メロディアス・ハードロック・バンド、ALYSON AVENUEでも活動していた、まだ当時は世界的には無名であったアネット・オルゾンを新たなヴォーカリストとして迎え入れることを発表、アネットを迎えた編成でバンドはまずシングル「エヴァ」を配信のみで発表、同年9月に6作目であり新生ナイトウィッシュの第一弾作品となる『ダーク・パッション・プレイ』を発表。そのオペラティックな歌唱法でカリスマ的人気を博していたターヤの後任に世界中から大きな注目が注がれたのだが、結果的に本国フィンランドだけで10万枚を超えるセールスを記録、各国でチャート1位を記録するなど、大きなセールスを記録するアルバムとなった。ここ日本でもオリコン総合チャート54位にランクイン、2008年には２度目となる来日公演を実施、大成功に収めている。

『ダーク・パッション・プレイ』に伴うワールド・ツアーは2009年9月まで続いたのだが、その合間となる2009年3月には本ツアーの模様を収録したライヴ作品『メイド・イン・香港』を発表している。そのツアーが終了した後、ツォーマスは次作用の曲作りに入っていく。2011年初頭から、アルバム・タイトルやアルバムのコンセプトといった断片的な情報が徐々にオフィシャル・ウェブサイトを通じて発表されていき、ファンの期待感を煽りながらアルバム制作を行っていく。そしてアルバム発売に先駆けて同年11月に、突如バンドはアルバムからの最新シングル「ストーリータイム」を発表、シングル・チャート1位を獲得する。そしてまず本国フィンランドで11月30日に、その他ヨーロッパでは12月2日に、そしてアメリカでは2012年1月10日、ここ日本では1月11日に、最新作『イマジナリアム』が発表を迎えた。