1998—2000

У красавіку 1998 года пачаліся здымкі першага відэакліпа на песню «The Carpenter», якія былі скончаны ў пачатку траўня.

У 1998 гаду бас-гітарыст Самі Вянскя, стары сябар Туомаса, далучыўся да групы. На працягу года песні для новага альбома былі гатовыя, і група паехала ў студыю ў пачатку жніўня. Запіс быў скончаны ў канцы кастрычніка. 13 лістапада Nightwish далі канцэрт у Китэе, і на гэтым канцэрце быў зняты відэакліп на песню «Sacrament of Wilderness». Аднайменны сінгл быў выпушчаны 26 лістапада, а затым, 7 снежня, быў выпушчаны новы альбом «Oceanborn».

Гэты альбом моцна адрозніваўся ад першага па тэхніцы выканання і па лірыцы. У запісы альбома прыняў удзел Тапіё Вільска з групы Finntroll. Яго вакал гучыць у кампазіцыях «Devil and the Deep Dark Ocean» і «The Pharaoh Sails to Orion». Песня «Walking In The Air» з'яўляецца каверам саўндтрэка да мультфільма «The Snowman» , напісанага Ховардам Блэйкам. Пачынальна з гэтага альбома, мастаком вокладак Nightwish з'яўляецца Маркус Майер (Markus Mayer).

Крытыкі былі здзіўленыя поспехам «Oceanborn». Ён падняўся да пятага месца ў фінскім афіцыйным чарце альбомаў, а сінгл «Sacrament of Wilderness» быў нумарам адзін у чарце сінглаў на працягу тыдні. Узімку 1999 года Nightwish далі шмат канцэртаў, гастралявалі па ўсёй краіне на працягу трох месяцаў. Увесну «Oceanborn» быў выпушчаны за межамі Фінляндыі. У траўні каманда пачала працаваць зноў, гастралюючы па ўсёй краіне на працягу двух з паловай месяцаў, выступаючы амаль на ўсіх вялікіх рок-фэстах. У гэты жа час быў запісаны сінгл «Sleeping Sun», які быў прысвечаны зацьменню ў Нямеччыне. У жніўні сінгл быў выпушчаны ў Нямеччыне, таксама на сінгл увайшлі песні «Walking in the Air», «Swanheart» і «Angels Fall First». Тады жа стала вядома, што альбом «Oceanborn» і сінгл «Sacrament of Wilderness» набылі статут «Залатога дыска». У той жа самы час Nightwish здзейснілі тур па Еўропе разам з нямецкай групай Rage.

У 2000 годзе Nightwish удзельнічалі ў адборы на конкурс песні Еўрабачанне ад Фінляндыі з песняй «Sleepwalker». Група ўпэўнена выйграла гледачовае галасаванне, але ў другім туры, галасаванні журы, была адсунута на другое месца і не дапушчана на конкурс.

Новы альбом «Wishmaster» быў выпушчаны ў траўні і пачаўся новы тур у падтрымку новага альбома. «Wishmaster» заняў першае месца ў чарце альбомаў і знаходзіўся на гэтай пазіцыі тры тыдні. За гэты час ён атрымаў статут «Залатой дыска». «Wishmaster» быў прызнаны фанатамі і крытыкамі, а ў шостым нумары часопіса «Rock Hard» за 2000 год быў названы альбомам месяца.

«Wishmaster» таксама дэбютаваў у нацыянальных нямецкіх чартах на 21 месцы і на 66 месцы ў Францыі. Сусветны тур «Wishmaster», які пачаўся з Китее, працягнуўся спачатку на вялікіх фэстах у Фінляндыі, а затым у Паўднёвай Амерыцы ў ліпені 2000 года. Трохтыднёвы тур па Бразіліі, Чылі, Аргентыне, Панаме і Мексіцы, як апынулася, быў адным з самых вялікіх досведаў групы. Усё гэта суправаджалася паспяховымі паказамі ў «Wacken Open Air», «Biebop Metal Fest». Гэтак жа група прыняла ўдзел у Еўрапейскім туры разам з Sinergy і Eternal Tears of Sorrow. У лістападзе Nightwish адыгралі два канцэрту ў Канадзе.