Construite en 1687-1688 sur l'emplacement de l'Habitation de Champlain et du Magasin du roi incendié quelques années auparavant, l'église est consacrée en 1690 à Notre-Dame-de-la-Victoire pour commémorer la défaite de l'amiral William Phips devant Québec. En 1711, à l'occasion du naufrage d'une grande partie de la flotte de l'amiral Hovenden Walker, elle est nommée Notre-Dame-des-Victoires.