En Groenlandia se corrió la voz de que un tal Björn Herjulfsson había encontrado unas nuevas tierras situadas más hacia el oeste, a cuyas costas fue arrastrado por una tormenta en un viaje entre Islandia y Groenlandia. Alrededor del año 1000 y con el mismo espíritu aventurero que su padre, Erik el Rojo, Leif embarcó acompañado de 35 hombres en busca de esas tierras.

Fue llegando a diversos lugares a los que denominó según fuese el elemento predominante del paisaje: Primero fue Helluland (Tierra Pedregosa), después Markland (Tierra de Bosques) y por último, Vinland (Tierra de Vides). Se supone que estos tres lugares son los que actualmente corresponden a Baffin, Labrador y Terra Nova. En esta última isla, concretamente en L'Anse des Meadows, se han descubierto restos de casas, unos 130 pequeños objetos y una herrería que puede fecharse justamente alrededor del año 1000, y que bien pudo servir de base para que aquellos hombres realizasen expediciones hacia el sur del continente.

En Vinland encontraron una tierra fértil con buen clima, donde los inviernos no suponían la interrupción de la vida cotidiana, con abundante pesca y caza. Era un lugar perfecto para iniciar una colonia. El nombre fue debido a unas vides salvajes que allí crecían, imposibles de encontrar en su tierra de origen.

Leif regresó a Groenlandia con el barco cargado de madera, un elemento muy necesario y valioso en esa isla, donde no había bosques, y uvas (algunos investigadores piensan que más bien debían ser algún tipo de bayas silvestres, de las que igualmente podía hacerse vino). Su padre había muerto y él, que por su hazaña recibió el apodo de el Afortunado, tuvo que hacerse cargo de la granja familiar, siendo su hermano Thorvald quien organizase la siguiente expedición.

Estos nuevos colonos, tras permanecer dos años en Vinland, construyeron nuevas casas y extendieron el territorio explorado. Al regresar a Groenlandia hicieron una parada en cierto lugar, donde tuvieron el primer contacto -desafortunado- con los indios nativos, a los que llamaron skraeling.

El tercer viaje estuvo a cargo de otro hijo de Erik el Rojo, Thorstein , pero el barco fue alejado de su ruta por una tormenta y finalmente todos los tripulantes, excepto una mujer, murieron a causas de una epidemia.

El cuarto viaje lo realizaron sesenta y cinco personas, al mando de Thorfinnur Karlsefni, en dos barcos bien equipados. Tras una temporada inicial que les debió parecer la vida en el paraíso, volvieron a hacer acto de presencia los skraeling, que pretendieron cambiarles pieles por sus espadas de hierro, que los indios desconocían. La negativa de los nórdicos ocasionó algunos problemas, hasta que la colonia nórdica decidió regresar a Groenlandia, después de tres años en Vinland, llevando consigo un buen cargamento de madera, que allí venderían a buen precio. En este viaje se produjo el nacimiento de Snorri, hijo de Thorfinnur Karlsefni y su esposa Grudrid, primer niño nórdico nacido en Vinland.

El quinto y último viaje documentado en las sagas estuvo protagonizado por Freydis, hermana de Leif. Esta expedición se hizo con dos barcos, perteneciendo el segundo a unos comerciantes islandeses. Pasaron un año, sin que hiciesen acto de presencia los skraeling, aunque no por eso eso tuvieron exentos de problemas, ya que Freydis se encargó de que las tripulaciones de los dos barcos (groenlandeses e islandeses) mantuviesen malas relaciones y andáran siempre con disputas por cualquier cosa. Finalmente convenció a su marido y a los suyos para que matasen a los groenlandeses, encargándose ella misma de matar a las mujeres que les acompañaban, quedándose así con toda la mercancía.