Skribu daŭrigon por ĉi tiu paragrafo - Elektita el la Quebec Major Junior Hockey League (QMJHL) 22-a ĝenerale en 1998
Gagné ludis ĉefajn junulojn kun la Beauport Harfangs kaj Quebec Remparts dum tri sezonoj. Li komencis sian NHL-karieron kun la flugiloj en 1999 kaj estis nomita al la NHL All-Rookie Team. Li aperis en du NHL All-Star Games kaj gajnis du Bobby Clarke Trophies kun la flugiloj kiel teamo MVP.