Le nom de cette rue évoque celui de la paroisse de La Nativité-de-Notre-Dame, fondée en 1684. À peu près à l'emplacement de l'église actuelle, on construit un premier temple en 1676. Détaché de la commune, le terrain est cédé par Robert Giffard, seigneur de Beauport, et par les habitants du bourg du Fargy, principal foyer de peuplement de la seigneurie. Dans l'acte de donation, l'église est appelée « Nostre-Dame de Beauport ». Toutefois, dans le décret d'érection de la paroisse, signé le 3 novembre 1684 par Mgr de Laval, on la désigne par le nom de La Nativité de la Bienheureuse Vierge Marie; le premier curé, Étienne Boullard, est nommé au même moment. En 1722, lorsqu'on établit les limites territoriales de la paroisse, il est plutôt question de « Notre-Dame de Miséricorde ». On finira par adopter le nom de La Nativité-de-Notre-Dame au cours des années 1950. En près de deux siècles et demi, cinq églises vont se succéder sur le même site, dont l'église actuelle, construite sur les vestiges de l'édifice incendié en 1916.

Plusieurs entités paroissiales seront créées à même le vaste territoire de La Nativité-de-Notre-Dame, dont Saint-Grégoire en 1890, Saint-Ignace-de-Loyola en 1914, Sainte-Thérèse-de-l'Enfant-Jésus en 1925 et Sainte-Gertrude en 1968. Certaines d'entre elles se regrouperont en 2001 avec La Nativité-de-Notre-Dame pour former la nouvelle paroisse de La Bienheureuse-Marie-Catherine-de-Saint-Augustin.