Formation und die ersten drei Alben (1986–1999)

Mystery wurde 1986 von Michel St-Père, der zu dieser Zeit bei „Studio Illusion“ als Ton-Ingenieur arbeitete, gegründet. Ursprünglich hieß die Band „Century“, wurde aber in Mystery umbenannt, nachdem herausgefunden wurde, dass bereits eine französische Band mit diesem Namen existierte.

Nach mehreren Wechseln in der Bandbesetzung wurde 1990 eine stabile Formation mit Michel St-Père (Gitarre), Stéphane Perreault (Schlagzeug), Raymond Savoie (Gesang) und Benoît Dupuis an den Keyboards gefunden. Richard Addison schloss sich 1991 als Bassist der Band an und Gary Savoie, Raymond Savoies Bruder, wurde Frontmann. 1992 wurde die gleichnamige EP veröffentlicht. Kurz darauf wurde Stéphane Perreault schwer krank und musste bis Herbst 1993 eine Auszeit nehmen.

1994 starteten die Aufnahmen für das erste Album der Band, Theatre of the Mind. Nach den Aufnahmen verließ Addison die Band und wurde durch Patrick Bourque ersetzt, der bereits bei dem Stück Rythmizomena des Debüt-Albums mitgespielt hatte. Als weiteres Bandmitglied kam Michel Painchaud hinzu und spielte Saxophon und Akustikgitarre.

1995 war die Band auf vier Mitglieder reduziert, da Dupuis und Painchaud die Band verlassen hatten. Um die Werbung für das erste Album zu verstärken, gründete Michel St-Père sein eigenes Musiklabel, Unicorn Digital, bei dem alle Mystery Aufnahmen seit diesem Zeitpunkt veröffentlicht wurden und werden. Mit der Veröffentlichung des Albums Theatre of the Mind wuchs der Bekanntheitsgrad der Band schnell über Kanada hinaus.

Während der Aufnahmen zum zweiten Album Destiny? verließ Perreault die Band und wurde auf Anraten des Toningenieurs Gilles Peltier durch Steve Gagné ersetzt. Im Mai 1998 wurde das Album Destiny? veröffentlicht und durch das französische Musiklabel Musea lizenziert. Kurz nach der Veröffentlichung stieß Anne Charbonneau als Keyboarderin zur Band.

1999 starteten die Aufnahmen zum nächsten Album, jedoch verließ Gary Savoie währenddessen die Band wegen musikalischer Differenzen.

Benoît David Ära (1999–2014)

Nachdem Gary Savoie die Band verlassen hatte, wurde er durch Benoît David ersetzt, den St-Père vorher auf einem Yes Tributkonzert der Band Gaïa (später Close To The Edge) kennenlernte. Michel St-Pères Fokus richtete sich nun auf sein Musiklabel, wodurch sich die Arbeiten am neuen Mystery Album verzögerten.

2000 veröffentlichte Mystery zwei Musikstücke: eine Coverversion des Songs Hey You für ein Pink Floyd Tributalbum sowie eine Demoaufnahme des Songs Beneath the Veil of Winter's Face für eine Progressive Rock Kompilation, der der gleichnamige Titelsong des nächsten Albums werden sollte. Außerdem veröffentlichte die Band das Kompilationsalbum At the Dawn of a New Millennium, das einen Wechsel der Stilrichtung der Band markierte.

Während der nächsten Jahre wurde weiter am neuen Album gearbeitet sowie eine Vorabversion des Songs As I Am auf dem Kompilationsalbum Prog-résiste veröffentlicht.

2006 veröffentlichte Mystery eine Coverversion von Visions of Paradise auf dem Moody Blues Tributalbum Higher And Higher: A Tribute To The Moody Blues.

2007 veröffentlichte Mystery am 15. Mai das dritte Studioalbum Beneath the Veil of Winter's Face. Im September des gleichen Jahres verstarb Patrick Bourque, der zugleich Mitglied bei der Band Emerson Drive war. Als Todesursache wurde Suizid angegeben. Als neuer Bassist wurde François Fournier in die Band aufgenommen, der Dean Baldwin als zweiten Gitarristen zur Band mitbrachte. Außerdem kam der frühere Keyboarder Benoît Dupuis wieder zur Band.

2008 wurde Benoît David neuer Leadsänger bei Yes (bis 2012) und ersetzte dabei Jon Anderson. Er blieb dabei aber Mitglied bei Mystery. Dies half der Band, ihren Bekanntheitsgrad weiter zu steigern, sie mussten jedoch ihre eigenen Aktivitäten nach dem Zeitplan von Yes richten.

2009 wurde das zweite Mystery Album Destiny? in einer neu abgemischten Version und mit neuem Schallplattencover sowie einem Bonus Musikstück als 10-Jahres-Jubiläumsausgabe wiederveröffentlicht. Die Band spielte außerdem als Vorgruppe von The Musical Box am 3. April 2009.

2010 wurde das vierte Album One Among the Living veröffentlicht, das sich als bis dahin bestverkauftes Album der Band herausstellte. Viele Gastmusiker waren an diesem Album beteiligt, wie z. B. Oliver Wakeman und John Jowitt.

2011 verließ Gagné die Band, da er sich außer Stande sah, die Aufnahmen zum nächsten Album zu begleiten, jedoch blieb er der Band als Tour-Mitglied erhalten. Die Aufnahmen zum neuen Album steuerte deshalb Nick D’Virgilio bei. Außerdem spielte Antoine Fafard (Spaced Out) alle Basslinien ein.

Am 28. Juli 2012 wurde Sylvain Moineau von der Band als neuer Gitarrist und Ersatz von Baldwin bekanntgegeben. Am 10. August 2012 veröffentlichte die Band das fünfte Studioalbum The World Is a Game.

Anfang 2013 wurde bekannt gegeben, dass Jean-Sébastien Goyette Schlagzeug bei Liveauftritten spielen und damit Gagné ersetzen wird. Der erste Auftritt mit dem neuen Schlagzeuger war am 7. Februar 2013. Eine neu abgemischte Version von At the Dawn of a New Millennium wurde am 26. Februar 2013 sowie ein neues Kompilationsalbum mit Werken der Band von 2007 bis 2012 veröffentlicht. Am 10. Mai 2013 spielte Mystery das erste Mal in Europa live in den Niederlanden während ihrer The World Is a Game-Tournee. Dieser Auftritt wurde als Doppel-Live-Album Tales from the Netherlands am 1. Oktober 2014 veröffentlicht.

Die Band (St-Père, Dupuis, Fournier, Moineau and Goyette) nahm den Gene Simmons Song See You Tonite mit dem Sänger Todd Farhood auf, der auf dem Kiss Tributalbum A World with Heroes veröffentlicht wurde.

Jean Pageau Ära (seit 2014)

Am 14. März 2014 wurde bekannt gegeben, das Benoît David die Band im Herbst 2013 verlassen habe, da er eine Pause vor der The World Is a Game Tournee wünsche. Jean Pageau, der Mystery 2013 als Vorgruppe zu Saga sah, wurde am 9. März 2014 als neuer Sänger bekanntgegeben.

Am 7. Juli 2014 wurde Antoine Michaud als Ersatz von Sylvain Moineau für alle Livekonzerte im Jahr 2014 bekanntgegeben.

Am 1. November 2014 veröffentlichte die Band das Album Delusion Rain. Von Ende September bis Anfang November tourte die Band in Kanada und Europa.

Am 3. April 2016 spielte die Band auf dem Progdreams V Festival in den Niederlanden, das als DVD Second Home am 7. August 2017 sowie als CD am 15. August 2017 veröffentlicht wurde. Dupuis verließ Mystery nach diesem Konzert.

Am 2. September 2016 spielte die Band auf dem 2Days Prog + 1 Festival in Veruno, Italien. Am 5. September des gleichen Jahres wurde Michaud als neuer Keyboarder und Ersatz für Dupuis bekannt gegeben.

Im August und September 2017 tourte Mystery durch Europa und Kanada und spielte zum 10. Jubiläum ihres Albums Beneath the Veil of Winter's Face alle Songs dieses Albums.

Am 7. September 2017 wurde bekannt gegeben, dass Mystery auf dem Night of the Prog Festival in Sankt Goarshausen 2018 spielen werden. Am Tag ihres Auftritts auf der Loreley, dem 14. Juli 2018, veröffentlichte die Band ihr siebtes Studioalbum Lies and Butterflies.

Bei der sich an die Album-Veröffentlichung anschließenden "Live and Butterflies"-Tour gab die Band zwischen November 2018 und November 2019 einige Konzerte in Europa und Kanada. Im Rahmen der Tour wurden zwei Live-Alben aufgenommen:

• Das erste Konzert der Tour am 17. November 2018 im Boerderij Cultuurpodium in Zoetermeer, Niederlande wurde erst 2 Jahre später, am 28. November 2020 mit dem Namen "Caught in the Whirlwind of Time" als Live- und Video-Album veröffentlicht.
• Das Album "Live in Poznań", das am 7. April 2019 im "Blue Note Jazz Club" in Poznań, Polen aufgenommen wurde.