Through ages without written history, native peoples had lived in little changing harmony with the forests, plains and mountains of a wilderness Canada. Then, around 1500 A.D., newcomers began arriving from across the North Atlantic, bringing with them powers of organization and technology far beyond those of the native societies. These migrants from Western Europe came from rising nation-states with fast-filling countrysides and busy towns. They navigated oceans, used metalware and firearms, knew mills and other machinery, and were increasingly advancing in arts and science. They carried transformation as they entered, though at first its pace was slow. The European fisherman who invaded Canadian Atlantic waters during the 1500s, the fur traders who probed on into the continent, the little posts and settlements that followed in their wake, for a long time did not seem to cause much change in the huge expanse of the wilds, nor in the lives of their original inhabitants. Yet, inescapably, the overseas arrivals were shaping another Canada, as their trade, territorial claims and colonies spread inward.

So it was that French and British migrants built up settled communities in the Canadian land mass from the early 1600s, while in the late 1700s the Loyalists, who moved north from a new-born United States, added more settlers of mainly European stock. By 1800, as a result, regions of Canada "from sea unto sea" had been acquired, or at least penetrated, by peoples and cultures of transatlantic origins. The roots of the present Canadian nation were set down over these founding centuries—if often at hard costs to former native holders of the land. The newly emerging Canada would, of course, grow and alter greatly after 1800. But by that date it had been firmly implanted by French, British and Loyalists: their efforts, abilities and aspirations, their expanding numbers and community life.

Forerunners of the transforming European invasion had reached Canadian shores long before 1500. There is clear evidence today that Norsemen, skirting cold northern coasts from settlements in Iceland and Greenland, got to Newfoundland by the 11th century. The proof lies at L'Anse aux Meadows, on a grassy inlet near the top of Newfoundland, where excavations have now revealed the remains of eight Viking sod-huts, traces of iron work, a bronze pin and a stone spinning whorl—suggesting that women as well as men lived in this lonely outpost, which existed for several decades. Nevertheless, neither the Norsemen or other possible early transatlantic voyagers left recognized, lasting impacts behind them. These did not come for several more centuries, that is, until Western European peoples, developing rapidly in shipbuilding and seamanship, made the broad North Atlantic an open highway to new resources, trade and power. In particular, enterprising fishermen from Atlantic ports sailed westward in quests for new fishing grounds to feed the mounting populations of their own countries. And in 1497 the Venetian Giovanni Caboto, or John Cabot, seeking a new western way to the Orient in the service of Henry VII of England, came instead upon the Grand Banks of Newfoundland, teeming with fleshy cod—a fishing ground of immense and enduring value.

Cabot's widely reported voyage sent fishing ships flocking to these trans-Atlantic banks, and gave England claim, as well, to this "New Found Land" beyond them. From 1500 on, fishermen yearly ranged the Newfoundland grounds, while others pushed into the Gulf of St. Lawrence, or established whaling at bays in Labrador. Thus, when Sir Humphrey Gilbert, in 1583, formally proclaimed England's title at the major fishing rendezvous of St. John's in Newfoundland, he did so in its sheltered harbour before 36 vessels of various origins, including Spanish, Portuguese and French as well as English. Yet England's claim to this island domain was increasingly made good by the spread of English fishing stations along the coastline on either side of St. John's: the "English shore", the eastern margins of the rugged Avalon Peninsula. Spanish, Portuguese and many French craft kept mostly to the banks fishery offshore, carrying "wet" fish, amply salted, directly to their homelands, with little resort to the coast except for fresh water and shelter. The English, however, took to the "dry" fishery, whereby lightly salted split cod were dried on shore over the summer for the return trip home. This produced a space-saving, long-keeping cargo. But more than that, it dotted English occupation around the eastern coves of Newfoundland, where drying racks went up, and huts for men to tend them. Here, as well, crewmen eventually wintered over, preparing for the next summer season when the annual overseas fishing fleet came in from England's southwestern ports.

Accordingly, year-round habitation gradually developed on the English Shore, while various fishery bases began to attract permanent residents, who were able to work a longer season, then sell their catch to visiting buyers. Organized settlement in Newfoundland only commenced in 1610, however, and grew very slowly, both because the summer fishermen from England resisted the interference and competition of resident rivals, and because governments in the home country supported the seasonal overseas fishery as a prime source of skilled seamen for the needs of war. Hence English colonization of Newfoundland was long impeded by the opposing power of the overseas fishing interest. Accordingly, the resident settlers on the island faced ruffian attacks, official neglect, and, for some time, even threats of removal.

Meanwhile, the French, who in part also practised dry fishing, had located shore stations beyond the well established English area, further westward along the island coasts or at adjacent mainland harbours. The latter drew Indians of the seaboard forests to trade furs for European cloth and metal goods, offering fishermen there a profitable extra cargo to take home—glossy beaver pelts. In the course of time, fur trading developed in its own right, especially when beaver proved plentiful and excellently suited for making fur-felt hats, which came widely into fashion in Europe before 1600. Overseas venturers turned from the sea's resources to those of the land, in its seemingly endless forests. In 1605 merchant interests in France founded Port Royal on the mainland beside the Bay of Fundy, a trading settlement in what the French knew as Acadia, and the English, later, Nova Scotia. But the French fur trade was to rise on a much larger scale on the far-reaching St. Lawrence River, which Jacques Cartier had explored and claimed for France in his voyages of 1534–35.