Podczas trasy koncertowej został zarejestrowany materiał na pierwszy w historii grupy album „live”. Zawierający 2 płyty CD Visions In Europe wydany został pod koniec marca 1998. Był on dużym sukcesem, zarówno komercyjnie, jak i artystycznie.
1998–2001 Od kwietnia 1998 roku zespół rozpoczął nagrywanie kolejnego, siódmego albumu studyjnego. Destiny nagrywany był przez wiosnę i lato tego samego roku. Pierwszy singiel SOS, zrealizowany 17 sierpnia, szybko wspiął się na trzecie miejsce najlepiej sprzedających się singli w Finlandii. Destiny zadebiutowało na pierwszym miejscu najlepiej sprzedających się albumów w Finlandii przed oficjalną premierą (5 października 1998). Na początku 1999 płyta pokryła się drugim w historii zespołu złotem. Był to początek sukcesów Stratovarius w tym roku. W fińskim magazynie „SFP” zespół wygrał głosowanie na najlepszy zespół metalowy w Finlandii, zaś teledysk do SOS został wybrany najlepszym metalowym teledyskiem w Finlandii w roku 1998. Po raz drugi Tolkki został wybrany najlepszym muzykiem w kraju. W kategorii „najlepszy zespół” Stratovarius uplasował się na drugim miejscu. Kotipelto zajął drugie miejsce w kategorii „najlepszy wokalista”. Destiny i SOS zajęły drugie miejsca w kategoriach: „najlepszy album” i „najlepszy utwór”. Tolkki i Kotipelto byli również nominowani w kategorii „Cudowna Osoba”.