Благодаря приверженности традициям в разрешении споров исландцы не только смогли избежать кровавой распри, но и не дали королю Олафу, который охотно вмешался бы, начнись в стране гражданская война, повода взять Исландию под власть норвежской короны. Более успешно Олаф управился с Фарерскими островами. В 1000 г. он отправил фарерского изгнанника, христианина Сигмундура Брестиссона, обращать островитян в новую веру и приводить под власть Норвегии. Вождем язычников на островах был Трондур из Готу, прилюдно проклявший христианство над молотом Тора. Однажды ночью Сигмундур со своими людьми ворвался в дом Трондура и предложил тому выбор: обращение или голова с плеч. Перед лицом столь убедительного богословского аргумента Трондур выбрал обращение, и другие фарерцы, поняв намек, последовали его примеру. Подобные методы убеждения вызывали у фарерцев ненависть, и в 1005 г. Сигмундура убили, но острова остались под властью норвежского короля.

После того, как скандинавы заселили Исландию, открытие Гренландии какими-нибудь заплутавшими норманнскими мореходами было уже только вопросом времени. Где-то между 900 и 930 гг. Гуннбьорн Улф-Кракусон, попавший в шторм и сбившийся с пути по дороге из Норвегии в Исландию, увидал в море к востоку от Исландии группу островов, которые потом в его честь называли Камнями Гуннбьорна. Принято считать, что это и был момент обнаружения европейцами Гренландии и, поскольку геологически остров принадлежит к Северной Америке, то и Американского континента. Точное местонахождение островов ныне неизвестно. Норвежский путешественник XIV столетия Ивар Бардарсон помещал их в двух днях плавания строго на запад от Снайфедльснеса, что на западном побережье Исландии. Если так, то, вероятнее всего, Камни – это архипелаг Сермилигаак, свободные ото льда острова напротив Тасилака, что на восточном берегу Гренландии, покрытом мощными ледниками. Гуннбьорн не высаживался на Камнях, и их открытие в его время не вызвало особого интереса, поскольку в Исландии оставалось довольно свободной земли: сам Гуннбьорн там и поселился. Однако население острова росло, и новым иммигрантам доставались все менее пригодные земли. В 975–976 гг. случилось холодное лето, трава росла плохо, и многие фермеры не смогли заготовить достаточно сена, чтобы скотина пережила зиму. Люди умирали от голода. Тогда исландцы заинтересовались Камнями Гуннбьорна, и в 978 г. Снебьорн Галти с 24 спутниками отправился на их поиски. Партия Галти построила на островах дом и провела там кошмарную зиму, погребенная под слоем снега до марта. Заточение никому не прибавило легкости нрава: люди ссорились, доходило до драк, и после того, как самого Снебьорна убили в стычке, неудавшиеся колонисты уплыли в Норвегию.

Первую успешную колонию в Гренландии основал рыжеволосый и рыжебородый Эрик Торвальдсон, более известный как Эрик Рыжий. Уроженец Норвегии, он еще ребенком оказался в Исландии: отца изгнали за кровную месть. Все лучшие земли на острове уже разобрали, так что семье Эрика пришлось поселиться на голом и льдистом юго-восточном берегу. Выросший Эрик не раз пытался занять землю получше, что оборачивалось спорами и распрями. Дело закончилось несколькими убийствами, так что в начале 980-х Эрика на три года объявили вне закона. Поскольку страну все равно пришлось бы покинуть, Эрик поплыл разыскивать Камни Гуннбьорна, пообещав вернуться, если найдет их. Он подошел к Гренландии с востока, недалеко от ледяного пика, позже прозванного Бласерк («голубая рубашка»): вероятно, это был Ригни-Бьерг, находящийся значительно севернее Полярного круга. Эрик двинулся вдоль неприветливого берега на юг и обогнул мыс Фарвель, самую южную точку Гренландии. Двинувшись вновь на север, он увидел фьорды, в укромных долинах которых обнаружились пастбищные земли и березовые леса. Берег был полностью необитаем, но Эрик нашел в нескольких местах остатки лодок и жилищ. Это были следы доисторических эскимосов (культура дорсет), столетием раньше покинувших те места из-за перемены климата. Скандинавская экспансия в Северную Атлантику совпала с началом Средневекового климатического оптимума, периода приблизительно между 900 и 1250 гг., когда климат в Североатлантическом регионе был теплее, чем в предшествующие и последующие века. Жизнь инуитов целиком зависела от охоты на морского зверя, которая бывает удачнее всего в конце зимы-начале весны, когда зверь хорошо виден на морском льду. С потеплением восточные фьорды почти очистились ото льда, и инуиты ушли на север к лучшим охотничьим угодьям.

Три лета Эрик исследовал Гренландию, а затем вернулся домой, надеясь убедить людей отправиться с ним и основать на Восточных фьордах поселения. Одаренный рекламист, он решил назвать остров Гренландией, то есть Зеленой землей, «потому что люди захотят туда поплыть, если у страны будет привлекательное имя». Исландия недавно пережила голод, и поэтому многие семьи откликнулись на призыв Эрика, так что следующим летом он повел к Гренландии 25 кораблей. «Книга об исландцах» сообщает, что было это за 14 или 15 лет до обращения Исландии в христианство, то есть около 985–986 гг. Из 25 отправившихся в путь судов до Восточных фьордов добрались лишь 14: остальные либо вернулись назад, либо пропали в море. Торбьорн, друг Эрика, приплывший в Гренландию через несколько лет после первых поселенцев, привез с собой на корабле 30 человек. Если это типичная загрузка корабля, то значит, началась гренландская колония чуть более чем с 400 пионеров. Этого, тем не менее, оказалось довольно, чтобы основать два поселения: одно покрупнее, Восточный поселок (Eystrbyggð) на юге, в районе нынешнего Какортока, и меньшее, Западный поселок (Vestribyggð) в 480 км севернее, у Нуука. Позже, на полпути между Восточным и Западным, появился небольшой Средний поселок. Жизнь устраивалась по исландскому обычаю, с ежегодным тингом, на котором Эрик председательствовал как бы в роли законоговорителя.

Имение самого Эрика находилось в Братталиде («косогор»), примерно в 100 км от морского побережья в оконечности фьорда Тунулиарфик, который во времена Эрика звался Эриксфьордом. Потомки Эрика жили в Братталиде до XV в. Археологи обнаружили там каменные фундаменты трех длинных домов и хозяйственных построек, предположительно определили площадку для тинга и кузню, нашли фундамент каменной церкви. Все каменные строения датируются приблизительно XIII или XIV в. По всей вероятности, жилище самого Эрика имело земляные стены, как тогдашние дома в Исландии, и его следы были уничтожены позднейшими постройками. Возле церкви располагалось кладбище, где насчитывается 144 захоронения, некоторые с каменными надгробьями: на одном из камней сделана короткая руническая надпись «Могила Ингибьорг». Примерно в центре кладбища археологи нашли следы совсем малой земляной церкви, внутреннее помещение которой было чуть больше 1,8 м в ширину и 3,4 м в длину. Земляные стены столь толсты, что внешние размеры церкви равняются примерно 3,7 м в ширину и 4,5 м в длину. Это здание напрямую связывают с женой Эрика Тьодхильд (еще одна исландка, которая прослеживала свое происхождение до Кербалла мак Дунлайнге). Около 1000 г. сын Эрика Лейф, посещая двор норвежского короля Олафа, крестился. Когда он собрался домой, король попросил его проповедовать в Гренландии новую веру и дал в попутчики священника, которому предстояло крестить и толковать учение. Эрик отнесся к обращению Лейфа прохладно и отказался принять чужую веру. А вот Тьодхильд сразу прониклась новым учением и построила на ферме небольшую церковь, где молилась сама и молились другие неофиты. Эрика обращение Тьодхильд раздосадовало еще больше: из-за его язычества жена отказала ему в близости.