Parti de Saint-Malo le 20 avril 1534 avec 61 hommes sur deux navires, Jacques Cartier est considéré comme le premier explorateur européen en terre canadienne (cependant, en 1497, Jean Cabot aurait circulé dans le golfe du Saint-Laurent).

Il planta une croix à Gaspé en 1534 et navigua sur le fleuve Saint-Laurent dès son second périple en 1535. Cartier s'aventura jusqu'au village d'Hochelaga (sur l'emplacement du futur Montréal) où l'équipage passa l'hiver : 20 personnes moururent du scorbut avant que Cartier n'obtienne des Iroquoiens du Saint-Laurent une recette (à base de feuilles de cèdre blanc) contre cette maladie.

Décidé à établir une colonie, le Royaume de France donna le commandement d'une nouvelle expédition à Jean-François de la Rocque de Roberval. La nouvelle colonie connut un hiver difficile qui coûta la vie à plus de 50 individus. Ayant d'autres préoccupations, en particulier les guerres européennes, la France cessa de s'intéresser au Canada pendant plus d'un demi-siècle. Cette période est communément appelée les « vaines tentatives ».

On peut affirmer que les débuts de la Nouvelle-France et, de par le fait même, du Canada, province de cette colonie, se situent plus précisément en 1600, quand le comptoir de Tadoussac fut fondé par Pierre de Chauvin, Sieur de Tonnetuit. Ce village est devenu réputé pour ses baleines, car bien situé au confluent de la rivière Saguenay et du fleuve Saint-Laurent.

Portrait de Jacques Cartier par Théophile Hamel, env. 1844

En 1603, les colons français, menés par Samuel de Champlain, s'allièrent aux tribus amérindiennes des Hurons-Wendats et des Algonquins contre les Iroquois. À cette époque, on comptait environ 30 000 Wendats et 15 000 Iroquois, mais une série d'épidémies abaissa la population des Wendats à 12 000 tandis que celle des Iroquois demeura inchangée.

En 1608, le père de la Nouvelle-France, Samuel de Champlain, fonda la ville de Québec qui était alors utilisée comme simple comptoir de traite. En 1627, la création par Richelieu de la Compagnie de la Nouvelle-France (ou des Cent-Associés) permit à cent actionnaires de développer le Canada.

L'année suivante, la première expédition, qui comptait 400 personnes, tomba entre les mains des Britanniques et ne parvint jamais à destination. À la suite de la capitulation de Québec face aux frères Kirke, les Anglais occupèrent le Québec et l'Acadie, de 1629 à 1632. Samuel de Champlain fut fait prisonnier et il s'ensuivit la faillite de la compagnie des Cent-Associés.

Champlain, le fondateur de la Nouvelle-France

À la suite du traité de Saint-Germain-en-Laye, le Royaume de France reprit possession de la colonie en 1632. La ville de Trois-Rivières fut fondée en 1634. En 1640, la Nouvelle-France ne comptait que 500 personnes. Les guerres iroquoises et les maladies ont été les principales causes de mortalité dans la colonie française.

En 1642, Paul de Chomedey de Maisonneuve fonda Ville-Marie (futur Montréal) qui n'était, à l'époque, qu'un fort servant de protection contre les attaques des Iroquois (la première grande guerre iroquoise dura de 1642 à 1667).

Carte géographique de la Nouvelle-France, dessinée par Samuel de Champlain en 1612.De 1627 et 1663, la population passa de 100 habitants à quelque 2500. En 35 ans, environ 1250 immigrants français vinrent augmenter la petite population d'origine; la natalité doubla le contingent.

Certaines provinces françaises jouèrent un rôle prépondérant : la Normandie, l'Aunis, le comté du Perche, Paris et l'Île-de-France, le Poitou, le Maine, la Saintonge, l'Anjou et la Bretagne, donc, surtout des provinces du Nord-Ouest, du Centre-Ouest, de l'Île-de-France et du Sud-Ouest. Les régions du Midi et des Alpes françaises ne participèrent que très peu.

Les immigrants provenaient principalement des régions côtières et des villes portuaires, ainsi que de la grande région parisienne.

Carte géographique de la Nouvelle-France, dessinée
par Samuel de Champlain en 1612

En 1663, le ministre des finances Jean-Baptiste Colbert mit en place un gouvernement royal en Nouvelle-France. Le territoire devait être administré comme une province française sous l'égide d'un gouverneur. En 1665, le régiment de Carignan-Salières (régiment d'élite) arriva dans la colonie dans le but de vaincre les Iroquois. En 1666, l'intendant de la Nouvelle-France, Jean Talon, organisa un premier recensement qui dénombra 3215 habitants.

Grâce aux politiques d'encouragement des naissances de Talon ainsi qu'à l'envoi par Louis XIV de 900 jeunes filles à marier, les fameuses Filles du Roy, la population de la colonie passa à 6700 habitants en 1672. En 1684, encouragés par les Britanniques, les Iroquois dirigèrent une seconde série d'attaques contre les établissements français.

En 1686, les Français s'emparèrent de trois forts anglais de la baie d'Hudson. Sous la gouvernance de Frontenac, les Français menèrent une série de raids contre les postes de la Nouvelle-Angleterre et chassèrent les Anglais de l'Acadie, de Terre-Neuve et de la baie d'Hudson. Cependant, en 1687, la France et l'Angleterre signèrent le traité de Ryswick qui mit fin à la première guerre intercoloniale.

En 1701, la paix fut signée avec les Iroquois. La colonie comptait moins de 15 000 habitants. Avec la signature des Traités d'Utrecht, en 1713, la France céda à la Grande-Bretagne l'Acadie (Nouvelle-Écosse), Terre-Neuve et la baie d'Hudson. De toute l'activité économique de la colonie, la traite des fourrures demeura l'activité dominante avec 70 % des exportations contre 20 % pour les produits agricoles.

La guerre de Sept Ans (1756–1763), entre la Grande-Bretagne et la France, prit un tournant décisif en Amérique du Nord. En effet, les colonies britanniques s'unirent pour en finir avec la Nouvelle-France. En 1755, ils déportèrent plus de 7 000 Acadiens vers la côte américaine, le gouverneur de la Nouvelle-Écosse (Lawrence), craignant leur intervention dans le conflit. En 1756, le général Louis-Joseph de Montcalm arriva en Nouvelle-France avec 3 000 hommes.

En 1759, le général britannique James Wolfe et son armée assiégèrent pendant dix semaines la ville de Québec qui capitula après une célèbre bataille sur les plaines d'Abraham (durant laquelle Montcalm et Wolfe furent blessés mortellement).

Le printemps suivant, en 1760, il y eut une tentative de reconquête, alors que le général Lévis, fort d’une nouvelle armée en provenance de Montréal, attaqua Québec. La dernière bataille ne fut pas décisive (259 hommes tués et 829 blessés du côté anglais, 193 tués et 640 blessés pour les troupes de Lévis). Les Anglais battirent en retraite vers la ville, laissant derrière eux les blessés.

Québec assiégée, Lévis croit que des navires en provenance de la France viendront leur donner du renfort. Ils ne viendront pas. Ce fut plutôt la flotte anglaise qui arriva avec plus de 18 000 hommes. Lévis leva le siège. Puis les Britanniques s'emparèrent de Montréal : la Nouvelle-France était conquise. La plus grande colonie française comptait alors environ 55 000 habitants. La population amérindienne, quant à elle, représentait alors environ 600 000 individus.