Chosen by King François I of France to lead an expedition in search of "gold and other riches" as well as a western passage to Asia, explorer Jacques Cartier set sail from Saint-Malo with two ships and 61 men in April 1534. After twenty days at sea, he caught sight of the island of Newfoundland, passed through the Strait of Belle-Isle between Newfoundland and Labrador, and travelled along the island's western coast, making the entire trip around the Gulf of St. Lawrence. During this initial voyage, he arrived in sight of Prince Edward Island and the coast of New Brunswick, sailed into what he named "Chaleur Bay," and landed on the Gaspé Peninsula, where he erected a cross on July 24, 1534, with the inscription "Long live the King of France." But this upset the natives, and Chief Donnacona (whom Cartier called "captain") told Cartier so. Cartier's account gives some idea of the natives' reaction to the cross erected in Gaspé:

We had returned to our ships when the captain came wearing an old black bear skin in a boat with three of his sons and his brother [...] and held forth at us, pointing at said cross and making a cross with his two fingers, and then pointing to the ground all around us as if he wanted to say that all the land was his and we should not have erected said cross without his permission.

Initial contact with the natives remained tentative, although Cartier obtained permission to bring two young Indians (Domagoya and Taignoagny) back with him. On his second trip to Canada (1535–1536), Jacques Cartier discovered many Amerindian fishing and farming villages dotting the north shore of the St. Lawrence, from the gulf to Hochelaga (Montréal) via Stadacona (City of Québec). The Micmac and Iroquois were suspicious of this foreign explorer seeking a route to Asian gold, silver, and copper reserves.

Linguistically, Cartier's voyages helped establish the toponymy of Eastern Canada very early; remember that Jacques Cartier introduced the toponym Canada to Europe. Below is linguist Marthe Faribault's (Philippe Joutard et Thomas Wien (Dir.), Mémoires de la Nouvelle-France, Presses universitaires de Rennes, 2005) description of Cartier, who was strongly influenced by Amerindian names:

In his second voyage (1535–1536), Jacques Cartier travelled up the St. Lawrence for the first time. He met Iroquois at Stadacona ("large cliff" in their language, now Québec City) and named the area the "Kingdom of Canada" from the Iroquois word kanata, meaning "village," while the Montréal area was named the "Kingdom of Hochelaga."

In the late 16th century, the Laurentian Iroquois withdrew from the St. Lawrence Valley. The Maritime Micmac, who had long travelled there over a portage road along the Restigouche, Matapédia, and Matane rivers or further south via the Etchemin and Chaudière river basins, became more present in the valley. Thus, toponyms from the Micmac language were adopted by the French in the late 16th and early 17th century. Gaspé, from the Micmac word gespeg meaning "extremity," replaced the Iroquois toponym Honguedo used by Cartier. Similarly, Québec—from the Micmac word gepèg meaning "strait"—replaced the Iroquois name Stadacona. Anticosti, from the Micmac word natigosteg("headland") replaced the toponym Île de l'Assomption given by Cartier. Last, Tadoussac—from the Micmac world giatosog meaning "between the rocks"—was named by the French around 1600.

Most of the Iroquois villages Cartier mentioned in 1536 no longer existed in 1608 when Samuel de Champlain founded Québec City. We know the natives had a strong warrior tradition. Their goal was rarely to gain land but generally to take prisoners. On his arrival in Canada, Champlain was quickly forced to take a stand in support of the Algonquin in their wars against the Iroquois. The Iroquois managed to virtually decimate the Huron, France's most loyal fur trading partners. The Inuit, Montagnais (Innu), Naskapi, Micmac, and Malecite also established lasting ties with the French, who had continuing difficulty maintaining peaceful relations with the Iroquois nations, at least until the Great Peace of Montréal in 1701.

The establishment of trading posts and missions altered relations between Amerindians and Europeans (mostly the French), especially in eastern North America in the pays d'en haut or Great Lakes region. This led to a rapid increase in trading and a growing mixed population. Speaking both local languages and French, the Métis became valued intermediaries between the Europeans and natives. The arrival of missionaries led to cultural and linguistic interference. While these men wanted to transform native culture into something more similar to the European Christian model, they learned native languages instead of trying to eliminate them. Nonetheless, the missionaries' arrival kicked off a systematic attack on the traditional religion, beliefs, and customs of native communities, not to mention the spread of disease. This attack continued and intensified when both French and British colonial governments took charge of "Indian affairs."