Ponadto, album był promowany w klubach promo „Passion and the Opera”.

W 1999 roku wydany został singel „Sleeping Sun”, mający związek z zaćmieniem Słońca widocznym w niemalże całej Europie. W samych tylko Niemczech singel sprzedał się w ponad 15 000 kopii w pierwszym miesiącu. W sierpniu płyta Oceanborn uzyskała status złotej.

W roku 2000 zespół wystartował w preselekcjach do Konkurs Piosenki Eurowizji z utworem „Sleepwalker”. Zajęli trzecie miejsce i nie pojechali na finał, mimo iż w głosowaniu publiczności zwyciężyli ogromną przewagą głosów. W maju grupa wydała kolejny album – Wishmaster. Zajął on od razu pierwsze miejsce na fińskiej liście przebojów i pozostawał na nim przez trzy tygodnie. W ciągu tego czasu zyskał również miano złotej płyty. Pomimo tego że w tym samym miesiącu wyszły też długo oczekiwane wydawnictwa grup Iron Maiden i Bon Jovi, to właśnie Wishmaster został uznany albumem miesiąca przez niemiecki magazyn „Rock Hard”. Jedynym oficjalnie wydanym singlem do tego albumu było Deep Silent Complete. Poza tym w klubach dostępne były jeszcze promo CD z utworami „The Kinslayer” oraz „Wishmaster”.

Rok 2001 był najcięższym w historii zespołu. Z zespołu musiał odejść Sami Vänskä, ponieważ miał konflikt z Holopainenem.