L'avenue Notre-Dame constitue le prolongement de la rue Notre-Dame, toponyme adopté en 1948 par le conseil municipal du village de Notre-Dame-de-Lorette (auj. la ville de L'Ancienne-Lorette) en remplacement de route de l'Église. La rue Notre-Dame tient son nom de la paroisse de Notre-Dame-de-l'Annonciation de L'Ancienne-Lorette, dont elle dessert une grande partie du territoire. L'église de Notre-Dame-de-l'Annonciation, érigée en 1907 sur le site du premier lieu de culte (1719), se dresse le long de cette voie, d'où l'ancien nom de route de l'Église. La paroisse voit le jour en 1698, mais ce n'est qu'en 1722 qu'elle obtient un statut officiel. Il semble que le vocable de Notre-Dame-de-l'Annonciation daterait de 1834. Il ferait allusion au sanctuaire de Lorette, en Italie, où la maison de la Vierge, lieu de l'Annonciation, a été transportée pièce par pièce de Nazareth à l'époque des croisades.

Le village et la paroisse de L'Ancienne-Lorette, qui formaient autrefois une seule entité municipale, sont devenus en 1947 la municipalité du village de Notre-Dame-de-Lorette (auj. la ville de L'Ancienne-Lorette) et la municipalité de la paroisse de L'Ancienne-Lorette, dont le territoire a été intégré à la ville de Québec.

Contrairement à ce qu'ont prétendu plusieurs auteurs, c'est à la dévotion à Notre-Dame que la rue doit sa dénomination et non à l'église Notre-Dame-des-Victoires située le long de cette voie. En effet, l'église est construite un demi-siècle après que le nom de rue Notre-Dame soit paru sur le plan de Québec dessiné en 1640 par Jean Bourdon. Pour ce qui est de la dévotion à Notre-Dame, elle se répand très tôt en Nouvelle-France, comme en témoignent plusieurs noms d'églises : Notre-Dame-de-Recouvrance (1633); Notre-Dame-de-la-Paix (1647); Notre-Dame-de-Québec (1664); Notre-Dame-de-la-Victoire (1690) – qui devient Notre-Dame-des-Victoires (1711) –, etc.

Ancien toponyme
L'avenue Notre-Dame constituait autrefois un tronçon de la route ou du chemin des Grands-Déserts, nom d'une ancienne concession. Le mot « désert » désignait anciennement un espace défriché prévu pour l'implantation d'un rang. En ce sens, il dérive de « essert » ou « essart », qui signifie défrichement, clairière en vue d'y établir la culture.