French interest in the New World began with Francis I of France, who in 1524 sponsored Giovanni da Verrazzano's navigation of the region between Florida and Newfoundland in hopes of finding a route to the Pacific Ocean. Although the English had laid claims to it in 1497 when John Cabot made landfall somewhere on the North American coast (likely either modern-day Newfoundland or Nova Scotia) and had claimed the land for England on behalf of Henry VII, these claims were not exercised and England did not attempt to create a permanent colony. As for the French, however, Jacques Cartier planted a cross in the Gaspé Peninsula in 1534 and claimed the land in the name of Francis I, creating a region called "Canada" the following summer. Cartier had sailed up the St. Lawrence river as far as the Lachine Rapids, to the spot where Montreal now stands. Permanent settlement attempts by Cartier at Charlesbourg-Royal in 1541, at Sable Island in 1598 by Marquis de La Roche-Mesgouez, and at Tadoussac, Quebec in 1600 by François Gravé Du Pont all eventually failed. Despite these initial failures, French fishing fleets visited the Atlantic coast communities and sailed into the St. Lawrence River, trading and making alliances with First Nations, as well as establishing fishing settlements such as in Percé (1603).

While a variety of theories have been postulated for the etymological origins of Canada, the name is now accepted as coming from the St. Lawrence Iroquoian word kanata, meaning "village" or "settlement". In 1535, Indigenous inhabitants of the present-day Quebec City region used the word to direct French explorer Jacques Cartier to the village of Stadacona. Cartier later used the word Canada to refer not only to that particular village but to the entire area subject to Donnacona (the chief at Stadacona); by 1545, European books and maps had begun referring to this small region along the Saint Lawrence River as Canada.