En 1535, deux jeunes autochtones indiquèrent à Jacques Cartier le chemin de « kanata ». Ils faisaient allusion au village de Stadacona, « kanata » étant simplement le mot qui désignait un « village » ou une bourgade dans la langue des Hurons ou des Iroquois. Faute d'une autre appellation, Cartier baptisa du nom de « Canada » non seulement Stadacona (emplacement actuel de la ville de Québec) mais également tout le territoire gouverné par son chef, Donnacona. Le nom en vint bientôt à s'appliquer à une région beaucoup plus étendue; en effet, sur les cartes de 1547, tout le territoire au nord du fleuve Saint-Laurent est appelé « Canada ».

Cartier avait également surnommé le fleuve Saint-Laurent la « rivière de Canada », nom qui fut utilisé jusqu'au début du XVIIe siècle. En 1616, bien que la région fut connue sous le nom de Nouvelle-France, le territoire bordant la grande rivière du Canada et le golfe Saint-Laurent était encore appelé Canada.