En 1535, Jacques Cartier s’est rendu à Hochelaga, alors comme aujourd'hui un centre rivalisant avec la colonie de Stadacona en aval du fleuve, dans ce qui est maintenant la ville de Québec. Il l'a décrite comme une communauté d’environ 1500 habitants entourée d’une palissade, et au cours de sa brève visite il a été mené par le chef du village au sommet de Mont Royal.

En 1609 et 1611, Samuel de Champlain a visité les sites de Kahnawake et Montréal (ce dernier marqué avec un A sur sa carte de 1612). Ici, il devait faire portage autour du « Sault Saint-Louis », les Rapides de Lachine, soulignant leur importance aux autochtones rassemblés pour faire diplomatie et commerce. L'importance diplomatique de l'endroit est commémorée dans le nom iroquoien Tiohtiagi, et celle commerciale est encore aujourd'hui une caractéristique importante de Montréal, située à l'entrée de la voie maritime.

Enfin en 1642, Paul de Chomedy de Maisonneuve, Jeanne Mance et environ 50 colons français ont commencé à bâtir une communauté sur le site marqué 30 ans plus tôt. La nouvelle colonie fortifiée fut nommée Ville-Marie, en célébration de la vision religieuse du Sieur de Maisonneuve et de Mgr de Laval.