In mid-985 or mid-986 an Icelandic flotilla led by Eric the Red set out to colonize southwest Greenland. Near summer's end Bjarni Herjolfsson, a trader, belatedly sailed to join them but was blown far off course. He coasted north to the latitude of southern Greenland, then turned east to complete his intended voyage, becoming the first European of certain record to have reached the American mainland. His first sighting of land was probably of Newfoundland, from which he coasted north at least to the termination of Labrador. The more southerly lands he found were well forested. About the turn of the century Eric's eldest son, Leif Ericsson, decided to exploit Bjarni's discovery.

Retracing Bjarni's route in reverse, Leif explored three distinct regions. In the north was Helluland, Land of Stone Slabs, an area that had nothing but glaciers, mountains and rock. This must be the area from the Torngat Mountains to Baffin Island. Farther south was Markland, Land of Forests, probably a large region around Hamilton Inlet in central Labrador. South of there was Vinland. Here Leif established a base camp from which he launched a systematic exploration of neighbouring areas. During his explorations he came upon wild-growing grapes wound around tall trees. Enchanted, he name the area Vinland, Land of Wine, and brought both wine and lumber back to Greenland.

Leif's voyage was followed by further expeditions, all led by members of Leif's family. The first was headed by his brother Thorvald, who was killed in a skirmish with aboriginal people. The second was by his brother Thorstein, who remained storm-tossed all summer and never reached land. A third expedition was under the command of Thorfinn Karlsefni, married to Gudrid, the widow of Thorstein. Karlsefni's expedition has been vastly glorified and magnified in the Eric's Saga version of the Vinland Sagas. The last recorded expedition was led by Leif's sister Freydis in partnership with two Icelandic traders. This expedition ended in disaster when Freydis had her people brutally slaughter her Icelandic partners and their crew.

Although distorted and incorporating elements from the Greenlanders' Saga, Eric's Saga and the Greenlanders' Saga complement each other with regard to details of the various expeditions. The base camp was called Straumfjord, meaning Current Fjord, and was located in the northern part of Vinland, probably in the Strait of Belle Isle area, at Epaves Bay on the northern tip of Newfoundland (see L'Anse aux Meadows). Another camp, used only in the summer, was Hop, meaning Lagoon, and located in southern Vinland. It was here that grapes and good timber were harvested for shipment back to Greenland. It was also here that the Norse encountered aboriginal people, with whom they had skirmishes sufficiently severe to make the Norse leave. Winters were spent at Current Fjord; summers were spent in reconnaissance and exploitation of resources to be shipped back to Greenland. A third location, mentioned only in the Greenlanders' Saga, is Leifsbuxir, or Leif's Camp. Leif's camp encompasses elements from both Hop and Straumfjord but is in essence synonymous with Straumfjord.

The Norse voyages to Vinland lasted only a few years, probably because the fledgeling new colony in Greenland, numbering only a few hundred, had no need for additional land. The resources of Vinland were too distant to be useful. Vinland was as distant from Greenland as was Norway, and the same products could be obtained in Europe where other necessities such as iron, grain, salt, and spices were also available. However, knowledge of the New World persisted among the Norse in Greenland, and there were occasional visits to Markland (Labrador) for lumber.