Peu après la fondation de Ville-Marie, les habitants utilisent un chemin qui borde la commune, une bande de terre d'un arpent (58,5 mètres) de largeur longeant le fleuve Saint-Laurent et la Petite rivière concédée aux habitants en 1651. Le Séminaire de Saint-Sulpice reprend ce terrain (une nouvelle commune sera créée au sud-ouest de la ville), et crée officiellement la rue Saint-Paul en 1673 selon un plan d’ensemble fait en 1672, en utilisant le chemin qui bordait déjà la lisière nord de la commune. Les nouveaux lots concédés du côté sud, sur le territoire de l’ancienne commune, feront ainsi face au chemin et à des propriétés existants. La rue homologuée se termine à l’ouest tout près de la rue Saint-Pierre, et à l’est au lieu de pèlerinage de Notre-Dame-de-Bon-Secours. Le chemin qui existait déjà se poursuit vers la campagne, à l’est et à l’ouest. Nommée Saint-Paul, cette rue évoque le souvenir de Paul de Chomedey de Maisonneuve, premier gouverneur de Montréal. Certains propriétaires, dont l'emplacement s'arrêtait au bord de l'ancienne commune, verront leur terrain prolongé jusqu'à la nouvelle rue. La rue elle-même sera prolongée vers l'est et vers l'ouest pour rejoindre les chemins des faubourgs Sainte-Marie et des Récollets. D'une largeur de 24 pieds français (7,8 mètres) à l'origine, plusieurs portions de la rue Saint-Paul seront élargies pour faciliter la circulation.

Contrairement aux rues bien droites qu'avait tirées Dollier de Casson l'année précédente, la rue Saint-Paul est un peu sinueuse. Centrée sur la place Royale, place de marché jusqu'en 1803, la rue Saint-Paul sera pendant longtemps la rue commerciale la plus importante de la ville. On y retrouve aussi des bâtiments de prestige tels que le palais de l'intendance (1698) et le château de Vaudreuil (1724). Au XIXe siècle, le Vieux-Montréal devient le berceau de la presse montréalaise. La rue Saint-Paul abrite une multitude de journaux de langue française et anglaise; on y imprime une douzaine de journaux politiques et littéraires. À cette époque, la rue Saint-Paul est toujours une rue très animée tant le jour que le soir. Elle est bordée de boutiques et elle est la seule à profiter de l'éclairage à l'huile.