Исландцы нашли в море самые надежный источник пищи, и они, естественно, исследовали воды вокруг своих островов. Возникли сказки об острове на западе, и действительно, там был огромный остров, всего в трехстах километрах к северо-западу.

С горных вершин на северо-западе Исландии можно было смутно различить землю на северо-западном горизонте, и в этой части острова жил в конце десятого столетия некий Эрик Торвальдсон. Его все называли Эриком Рыжим, из-за цвета волос.

В 982 году Эрика изгнали за какое-то преступление, и он решил использовать трехлетний период вынужденного изгнания для того, чтобы отправиться в путешествие на запад. В конце концов он добрался до далекого острова, но обнаружил, что его побережье покрыто льдом, который мешал высадке. Он плыл вдоль берега на юго-запад, пока не добрался до мыса, который мог обогнуть, затем поплыл вдоль западного побережья на север. Югозападное побережье было менее пустынным, и Эрик решил, что оно способно прокормить колонию.

К 985 году Эрик вернулся в Исландию и зазывал колонистов на свою новую землю. Для этого он нагло преувеличивал ее привлекательные качества, даже назвал ее Гренландией, зеленой страной. В действительности же Гренландия, самый крупный остров в мире, — это огромная пустыня, покрытая почти целиком колоссальным ледником, толщиной в несколько километров. Это один из последних остатков ледникового периода, и только Антарктида еще более пустынна. С другой стороны, северный климат тысячу лет назад был мягче, чем сейчас, и полоса вдоль юго-западного берега Гренландии, возможно, была не намного хуже Исландии.

Во всяком случае, Эрик нашел добровольцев, желающих поселиться на новой земле, и в 986 году он отправился на запад с двадцатью пятью судами. Четырнадцать кораблей добрались до нее, и колонию основали на западном берегу острова, у его южной оконечности.

Колония в Гренландии находилась на широте южнее широты Исландии километров на восемьсот. Но в то время, как Исландию омывает кончик теплого Гольфстрима, Гренландии досталось холодное Лабрадорское течение. Тем не менее викинги-колонисты держались и упорно прожили там более четырех столетий. В самые лучшие времена, около 1200 года, на острове могло проживать целых 3000 викингов.

Пока существовала гренландская колония, она служила базой для исследовательских путешествий еще дальше на запад. Около 1000 года один викинг по имени Бьярни Херьюльфсон рассказывал сказку о том, как он плыл из Исландии в Гренландию, как его застал шторм и пронес мимо оконечности Гренландии, а потом еще дальше на запад. Ему удалось сделать разворот и вернуться в Гренландию, но до этого он заметил землю к западу от Гренландии.

Эту сказку слушал Лейф Эриксон, сын Эрика Рыжего. Он побывал в Норвегии, где его обратили в христианство, а теперь вернулся в Гренландию. Его воображение поразила сказка Бьярни, поэтому он купил корабль Бьярни, собрал команду из тридцати пяти человек и отправился исследовать западные земли.

Он добрался до той земли, о которой говорил Бьярни. Сначала он встретил довольно бесплодный берег Лабрадора, но поплыл на юг к более приветливой территории и, вероятно, достиг северной оконечности Ньюфаундленда.

В то, что Лейф достиг Лабрадора и Ньюфаундленда, поверить очень легко. Большой загадкой этого исследовательского путешествия (по крайней мере, как его описывают в более поздних легендах) было открытие земли, где обильно рос дикий виноград. Этот район, где рос дикий виноград, Лейф назвал Винландом.

Возможно, сказка о виноградных лозах была всего лишь попыткой сделать эту землю более привлекательной для поселенцев (следуя прецеденту, созданному отцом Лейфа, Эриком Рыжим). Или рассказ мог быть приукрашен позднее. Но если этот отчет соответствует истине, это вызывает вопросы, так как дикий виноград не растет так далеко на севере, где расположен Ньюфаундленд, и совсем невероятно, что он рос там тысячу лет назад.

Некоторые считают, что Лейф действительно нашел дикий виноград, а это означает, что он проник намного южнее Ньюфаундленда, возможно, даже до современного штата Нью-Джерси.