Il marque 11 buts, un sommet pour lui dans la LNH, dès sa première saison avec les Canadiens, ce qui lui vaut de remporter le Trophée Jacques-Beauchamp, remis au joueur ayant joué un rôle déterminant dans les succès de l’équipe sans en retirer d’honneur particulier. Il brise de nouveau son propre record avec 22 buts et 43 points récoltés durant la saison 2016-2017 et atteint de nouveau le plateau des 20 buts lors de la saison 2017-2018, se méritant le Trophée Jacques-Beauchamp pour une deuxième fois en trois ans[2]. Il réalise également son premier tour du chapeau le dans une victoire de 10 à 1 contre les Red Wings de Détroit[3]. Le , il devient capitaine adjoint des Canadiens de Montréal[4].
Le 16 janvier 2019, il est suspendu trois matchs pour assaut à l'endroit de MacKenzie Weegar des Panthers de la Floride. En effet, lors de la mise en échec, les patins de Byron quittent la glace alors que Weegar n'a plus la rondelle[5]. Weegar se venge le 26 mars 2019 en lui assénant un uppercut qui le met K.-O. lors d'un combat de très courte durée[6].
Les blessures s'accumulent par la suite et en été 2021, Byron subit une chirurgie à la hanche. Il ne joue que 27 matchs la saison suivante et aucun match lors de la saison 2022-2023[7]. Il annonce sa retraite le [8]. Le jour même de son annonce, les Canadiens dévoilent qu'il devient consultant au développement des joueurs. Au cours de sa carrière dans la LNH, l'Ottavien aura cumulé 208 points dont 98 buts en 521 matchs.
Famille
Paul Byron a comme épouse Sarah Leblond et il a deux enfants. Sa fille se nomme Elianna et le nom de son fils est Brysen.