Au début des années 1670, le Séminaire de Saint-Sulpice, responsable spirituel de Ville-Marie depuis 1657 et seigneur de l'île de Montréal depuis 1663, souhaite ériger une église paroissiale. La chapelle de l'Hôtel-Dieu avait jusqu'alors servi de lieu de culte pour la population. Les Sulpiciens choisiront d'ériger la nouvelle église sur le coteau. Par la même occasion, ils redessinent la trame urbaine afin de faciliter l'accès à l'église située au coeur de la nouvelle grille et de régulariser le développement de la ville selon un plan orthogonal.

En juillet 1672, François Dollier de Casson, supérieur du Séminaire, accompagné de l'arpenteur et greffier Bénigne Basset, définit les nouvelles rues, leur donne des noms et appose des bornes. La rue Notre-Dame est la première rue tracée par Dollier de Casson. Elle suit l'ancien chemin du coteau Saint-Louis vers l'est de la ville et devient l'un des trois grands axes qui traversent la ville d'est en ouest. Étant la principale artère de Ville-Marie, il lui donne le nom de Notre-Dame en l'honneur de la Sainte Vierge, patronne de la paroisse.

À l'origine, large de 30 pieds français (9,7m.), la rue Notre-Dame allait de l'actuelle rue Bonsecours jusqu'au delà de la rue McGill. Au moment de la démolition des fortifications (1804-1810) et du nivellement de l'ancien coteau de la citadelle, les rues Saint-Joseph (à l'ouest) et Sainte-Marie (à l'est) dans les faubourgs voisins sont rattachés à la rue Notre-Dame. Au XVIIe et au XVIIIe siècle, on retrouve sur la rue Notre-Dame les communautés religieuses masculines de Montréal : les Récollets à l'ouest, les Jésuites à l'est et les Sulpiciens au centre. Après la Conquête, l'administration civile établit une présence importante sur cette rue avec, au fil des ans, la construction des prisons, des palais de justice, et de l'hôtel de ville. Au XIXe siècle, la rue Notre-Dame devient la rue principale pour le commerce de détail. La rue est aussi élargie par la Ville grâce à une série d'expropriations et d'achats de terrains, notamment du côté nord au cours des années 1860. À cause de sa largeur, et du fait qu'elle mène à l'église paroissiale, la rue Notre-Dame sera le haut-lieu des processions religieuses, manifestations et parades de toutes sortes. On note entre autres, la procession funéraire de Thomas D'Arcy McGee en 1868 et de celle de George Étienne Cartier en 1873.