The saga of the Greenlanders tells that Leif set out about 1000 to follow Bjarni's route in the opposite direction. The first land he met was covered with flat rock slabs (Icelandic:hellur). He therefore called it Helluland (land of the flat stones), which is probably the present day Baffin Island. Next he came to a land that was flat and wooded, with white sandy beaches, which he called Markland (woodland), which is assumed to have been Labrador.

When they found land again, Leifur and his men landed and built some houses. They found the land pleasant: There was plenty of salmon in the river, and the climate was mild, with little frost in the winter and the grass remaining green. They remained at the place over the winter.

The sagas mention that one of Leifur's men, Tyrkir, a German, found grapes. Leifur named the country Vínland after it. On the return voyage, Leif rescued a Norse castaway, which gained him the nickname 'Leifur the Lucky'.

There is discussion as to the location of Leifur's Vinland. Many believe that the Norse settlement at L'Anse aux Meadows was Leifur's colony, but others argue that it must have been more southernly, since grapes do not grow as far north as Newfoundland.

Another saga, Eirik the Red's saga tells that it was actually Leif who discovered the American lands, while returning from Norway to Greenland in 1000 or thereabouts, but does not state an attempt of his to settle there.

However, the saga of the Greenlanders is nowadays considered to be the more reliable of the two. As far as known, Leifur Eiríksson had two brothers, Þorvaldur and Þorsteinn, and one sister, Freydís. He married Þórgunna and had one son, named Þorgils.