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