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