Bjarni told the story to Eric the Red's son Leif (Leifr Eiríksson), who pricked up his ears at the mention of the timber, something the Greenlanders were chronically short of. The two sagas that tell the story, the Saga of the Greenlanders (Grœnlendinga saga) and the Saga of Eric the Red (Eiríks saga rauða) disagree on a lot of the details, but some fifteen years later, in 1000, Leif bought some ships from Bjarni, hired some of his crew, and retraced his route. There seem to have been two expeditions, the second about 1010 led by Thorfinn Karlsefni, an Icelander who had married Eric's daughter-in-law Guðríðr, and in which they discovered and took possession of three places. The first they called Helluland ("flatstone land" - Baffin Island?) The second they called Markland, which probably means "wood land"; scholars think this may be Labrador, which at that time had trees closer to the coast than it does now. Finally they settled in what they called Vinland. Both Adam of Bremen and the sagas say this was named for grapevines (vín, "wine"), but it may have been pastureland, vin. According to the Saga of the Greenlanders the settlement was simply called Leifsbuðir; according to the Saga of Eric the Red there were two, a northern one called Straumfjörðr, "stream-fjord" and a warmer southern one called Hóp, "lagoon" or "estuary."

The sagas do talk of wild grapes, and also of wild wheat and plentiful salmon, and they say it did not snow and the animals were able to graze all winter. However, there were several attacks by natives, whom they called skrælingar. They were in skin boats, armed with sticks that they spun around so that it sounded like threshing, and are described in the Saga of Eric the Red as "small, [dark,] ill-favoured men, [with] ugly hair on their heads. They had big eyes and were broad in the cheeks." They sound like Inuit rather than Indians. The Norse fought them off and traded them cloth or milk (depending which saga one reads) for skins, but refused to sell them swords or spears. In the Saga of Eric the Red, one of the few women with them, Leif's sister Freydís Eiríksdottir, puts on a magnificent display that enables them to get the better of the skrælings: she comes out of her hut in her shift, screaming that the men are all cowards and should let her take part in the battle, but they will not give her a weapon and being heavily pregnant, she cannot keep up with them. So she heads into the woods, the skrælings following her, finds a dead Norseman lying there felled by a stone and takes his sword, then yanks her neckline down and beats the flat of the blade on her breasts. The skrælings take flight in consternation. However, in the Saga of the Greenlanders she is painted as a grasping cheat who undermines the expedition by trying to take more than her share, and conflicts over the women, along with awareness that they were vastly outnumbered by the skrælings and would always have trouble with them, led the Norse to rapidly abandon Vinland, although by some accounts people talked of returning to get timber as late as 1300. One child was born in Vinland, Thorfinn and Guðríðr's son Snorri, the first white American.

In 1960, the archeologists Helge and Anne Stine Ingstad discovered what proved to be a Norse settlement at L'Anse aux Meadows in northern Newfoundland. This was excavated in the 1960s and 1970s and most scholars now believe it is Vinland, although some still prefer a more southern location, particularly Massachusetts because of the Chilmark runestone (generally believed to have been a fake). (The mouth of the Hudson and Chesapeake Bay have also been suggested.) They argue that L'Anse aux Meadows must have been a later outpost, not the original settlement. It is hard to believe the climate of Atlantic Canada was so much warmer a thousand years ago, but quite possible, especially if it was "pastureland," or if the "grapes" were some other fruit that could be made into wine, such as gooseberries or even blueberries (both still plentiful in the area). The voyage to Canada would have been much shorter.