Il devient d'ailleurs champion de
France dans cette discipline en 1995. En 1998, Grégory Lemarchal s'inscrit à l'émission de télécrochet « Graines de Star » de la chaîne de télé française M6, mais il en ressort bredouille... Cependant son passage à la télévision lui permet d'acquérir une certaine notoriété dans la ville de
Grenoble et dans ses environs. Pour preuve, on lui propose de participer à des spectacles aux côtés d'artistes français populaires tels qu'Hervé Vilard et
Gilbert Montagné. Après avoir été retenu au casting de la Star Academy 2004 de
TF1, Grégory Lemarchal ressort grand vainqueur de la quatrième saison avec 80% des votes du public. Universal, la nouvelle maison de Grégory Lemarchal, le prend sous son aile pour l'enregistrement de son premier album « Je Deviens Moi ». Entièrement écrit et composé par Yvan Cassar, l'album comporte également une reprise de la chanson allemande « Liebe ist Alles » de Rosenstolz, intitulée « Je Deviens Moi », tout comme l'album. Grégory Lemarchal part ensuite trois mois en tournée avec l'équipe de la Star Ac.