Ce toponyme a été adopté dans le cadre de l'harmonisation des noms de rues, rendue nécessaire par le regroupement municipal du 1er janvier 2002.

Paul de Chomedey de Maisonneuve (1612-1676), fondateur et premier gouverneur de Montréal. Originaire de la Champagne, Maisonneuve arrive au Canada en 1641. Au printemps de 1642, avec Jeanne Mance et madame de la Peltrie ainsi que plusieurs autres collaborateurs, il fonde un établissement qui donnera naissance au bourg de Ville-Marie, la future ville de Montréal.

Ancien toponyme
La rue Paul-De Chomedey portait auparavant le nom de rue De Chomedey, adopté vers 1954, en l'honneur du même personnage.