Destiny?

Mystery's lineup changed drastically from their previous album Theatre of the Mind, having only two of the same members: guitarist Michel St-Père and singer Gary Savoie. Bassist Richard Addison left the band in 1994 after finishing his parts for Theatre of the Mind and was replaced by Patrick Bourque, who played as a session musician on the album. Keyboardist Benoît Dupuis and acoustic guitarist and saxophonist Michel Painchaud left the band in 1995, leaving the band with four members. Then, drummer Stéphane Perreault left during the recording sessions for Destiny?. Gilles Peltier, the owner of a studio at which Mystery was recording, knew Steve Gagné and suggested him as at least a temporary replacement for Perreault so the current album could be finished. Gagné was given three songs to learn in a short period of time and when his recording of the tracks was heard it impressed St-Père and Savoie very much, leading Gagné to become a full-time member of the band.[4]

Two songs were recorded during the recording sessions for the album that did not appear on its original release: "Heaven Can Wait" and "Beneath the Veil of Winter's Face". "Heaven Can Wait" was released as a bonus track on the 10th Anniversary Edition of the album in 2009 while "Beneath the Veil of Winter's Face" became the title track of the band's next album.

The original cover design was done by Mystery's previous drummer Stéphane Perreault.[5] When the album was rereleased in 2009 it was given new artwork, with the photograph from the original release being displayed on the television screen.