Рассказ Бьярни чрезвычайно заинтересовал недавних поселенцев Гренландии. Около 1000 г. Лейф Эрикссон, сын Эрика Рыжего, «встретился с Бьярни Херъёлфссоном, купил у него корабль и нанял команду; всего насчитывалось 35 чел.». Они пошли на запад от Гренландии и «первой обнаружили землю, которую Бьярни видел последней, спустили лодку и вышли на берег, однако не нашли там травы. Горы покрывали огромные ледники, а между ледниками и берегом вся суша казалась одним единым камнем. Земля явно не имела ценности». Лейф назвал ее Хеллюланд (Ровная Каменная Земля).
Двигаясь на юг, они «обнаружили вторую землю» и там тоже высадились. «Местность была ровной и покрытой лесами и всюду, куда бы ни шли они, попадались белые песчаные берега, под небольшим углом уходившие к морю». Лейф нарек ее Маркланд (Лесная Земля). Они снова поставили парус и «шли при северо-восточном ветре два дня, когда вновь увидели сушу». Команда причалила к ней, оставила ладью и отправилась обозревать окрестности. Викинги нашли реку, которая, как они обнаружили, поднявшись по ней, «вытекала из озера». Лейф со спутниками выгрузили привезенные с собой снасти и принялись сооружать хижины. «Позднее они решили зимовать там и построили большие дома». Первое поселение викингов в Новом Свете получило название Лейфсбудир. Сама по себе природа показалась им «такой благодатной, что они предположили, что там даже не придется заготавливать корм для скота на зиму. Зимой заморозки не беспокоили, а трава почти не жухла. Продолжительность дня и ночи имели более ровные пропорции, чем в Гренландии и в Исландии». При детальном рассмотрении оказалось, что там растут «виноградные лозы и дают плоды», что подтолкнуло путешественников назвать землю Винланд. Весной они нагрузили корабль лесом и отправились назад, в Гренландию. На пути домой спасли команду другого судна.
Страндхёгг на скрэлингов
Если верить сагам, викинги предприняли в Винланд из Гренландии еще по меньшей мере четыре похода, предположительно датируемых периодом с 1000 по 1030 г. Первую экспедицию возглавил брат Лейфа Торвальд, который вместе с 35 чел. команды отыскал дома, построенные Лейфом в Лейфсбудире. До сего времени викинги еще не встречали следов другого человеческого жилья в новых землях, пока однажды поисковая партия не обнаружила «на острове к западу сделанное из дерева хранилище для зерна», которое совершенно очевидно являлось делом рук человека. Следующим летом Торвальда с товарищами ждала волнующая встреча с местными жителями Нового Света. На берегу они наткнулись на «три кожаных лодки, под каждой из которых находилось по три человека». Торвальд со спутниками напали на аборигенов и «захватили их всех, кроме одного, сбежавшего на кожаной лодке». Согласно «Саге о гренландцах», так состоялся первый контакт европейцев с исконными жителями Америки.