在一次偶然的经历中，维京人发现了冰岛，现在他们以同样的方式发现了西北部更远处的岛屿。传说9世纪初时，第一个维京人发现了这些群岛，这个人来自挪威，名叫贡比约恩·乌尔夫松（Gunnbjϕrn Ulfsson）。在从挪威到冰岛的航行中，贡比约恩遇上了风暴，颠簸了很久之后，他看到了那些乱石嶙峋的岛屿，此前并没有人知道这些岛屿，后来他用自己的名字给岛屿命名为“贡比约恩群岛”。他还发现群岛西部有一块更大的陆地，但后来他将自己的所见说给别人听时，却没人对此感兴趣，因为那时的冰岛土地还很充裕。
差不多一个世纪以后，冰岛开始面临人口过剩的问题——至少在维京人看来是这样。978年，斯兰约恩·加尔蒂（Snæjörn Galti）决定去寻找贡比约恩所说的那块神秘的陆地，并打算如果能找到这块陆地，他会将其作为自己的殖民地。招募了几个船员之后，斯兰约恩就开始朝着贡比约恩群岛航行，他希望可以在岛上得到附近那块陆地的消息。这时候的贡比约恩群岛人烟稀少107，居民都是一些因为冰岛太拥挤才来到这儿的人，他们确信群岛西部的确还有新大陆。
功夫不负有心人，斯兰约恩的坚持最终起了成效，经过几天的航行之后，他来到了格陵兰岛东海岸。这是一块非常辽阔的火山岛，面积比整个斯堪的纳维亚半岛都要大。他在这儿建立了自己的殖民地，但灾难很快就降临了。他选的这块地方并不好，因为格陵兰岛东海岸非常不适合人类居住。更致命的是殖民者之间起了内讧，互相残杀。两派殖民者之间发生了激烈的争执，没人知道确切的起因是什么，但双方都动用了武器，斯兰约恩在打斗中丧生。殖民者群龙无首，这块殖民地也就分崩离析，只有两名幸存者回到了冰岛。
殖民格陵兰岛的伟大构想虽然失败了，但这次尝试证明了贡比约恩所说的那块新大陆的确存在，而且从冰岛出发就能到达。仅仅四年之后就有人再次进行了这样的尝试，并且获得了成功。这次的远航由埃里克·索瓦尔松（Erik Thorvaldsson）领导，他是挪威人，生性鲁莽，人们都管他叫“红胡子”埃里克。鲁莽这一特性似乎在这个家族的血统中代代传承，埃里克的父亲索瓦尔曾因过失杀人罪在挪威遭到流放，短短几年之后，埃里克又重蹈了父亲的覆辙，也因为“杀了几个人”遭到驱逐。为了寻求庇身之所，他逃到了冰岛，然后在岛屿的西北部弄了块土地，准备长期定居。
然而，无论埃里克走到哪里，麻烦似乎总是如影随形。在他的第一个农庄上，两个奴隶在干活时不小心将一块巨石弄下了山坡，砸坏了邻居家的房屋。邻居要求埃里克对此做出赔偿，但他却杀了人家——此人有个滑稽的外号“缠人鬼”伊约尔，他又得逃离了。埃里克这次逃到了远离冰岛的一个小岛上，伊约尔的家人绝对不会找到这里来报仇。
较第一个农庄而言，埃里克在新农庄的经历更为不顺，因为他很快又与人起了争执。这一次他不仅杀了他的邻居，还把邻居家的儿子也杀死了，最后埃里克被判流放三年。108
埃里克逃离了那些会因为杀人罪驱逐他的地方，显然，他需要的是一块没有现行法律的地方，所以他买下了斯兰约恩的船只，同时还雇用幸存的船员，然后他们便朝西驶去。航行中，这些有经验的水手尽量按照上次的航线前进。流放的三年中，埃里克一直沿海航行，希望可以找到一块适合开垦殖民地的土地。终于在绕过南部的一块冰角，即现在的费尔韦尔角之后，他在与冰岛纬度相当的西海岸发现了两处适合人类居住的海湾。
埃里克当时可能还未意识到他已经抵达新的岛屿，因为这块小岛周围有很多浮冰，他的船只没法靠近，但他注意到这是块“处女地”——这里没有人迹109，也没有食肉动物；埃里克深信自己可以在这儿建立殖民地了，于是他又返回冰岛，招募一些移民来跟他一块儿居住。
和所有善于推销的人一样，埃里克深知宣传的重要性。为了让这块新陆地能吸引更多的人，他将此地命名为“绿色之地”（Greenland,音同格陵兰）。这个办法成效卓著，有500多名冰岛居民表示愿意同埃里克前往。埃里克能招到这么多的同行者，一方面是因为他极力劝说，把格陵兰岛描绘成一个“鱼鳖不可胜食”的天府之地；另一方面则是因为人们一直都想占领尚未开垦的新土地，后面一点格外重要，因为冰岛已经没有优质的土地可供占领了。那时的冰岛已经显露出生态恶化的迹象，为了拥有更多的草场，岛上的居民已经将所有的桦树林伐为平地；因为大肆砍伐森林，山地的土质也开始退化。冰岛上不再有未被开垦的土地，连一些新开垦的农庄也因为土壤退化的原因纷纷倒闭了。
985年，埃里克率领一支由25条船组成的庞大舰队从冰岛出发，船上满载在西部岛屿开始新生活的各种必需品。旅途异常艰险，跟随埃里克而去的人都清楚前路难测，风险重重，他们得在巨浪滔天的大海上行驶上千英里。最后在25只船中，一共有18只安全抵达了格陵兰岛。移民者刚把船只停靠在沙滩上，就已经感到了些许的失望。
现在他们才知道埃里克当初的描述有多么言过其实，如果说冰岛只是勉强能居住的话，格陵兰岛就是完全不适合人类居住。岛屿大部地处北极圈以北，维京人几乎不具备在这里生存下去的技能。尽管格陵兰岛非常辽阔——占地4.08万平方英里，是世界上最大的岛屿，但几乎所有的土地都不适合人类居住：广阔的内地为冰川所覆盖，只有沿海50英里宽的地方没有冰川，但却山岳林立，寸草不生；岛上几乎没有木材和铁矿，一年之内温暖的季节太短，不宜种植小麦或其他主要作物。如果他们的必要物资用完了，就得从冰岛进口，这在10世纪来说是件非常困难甚至不可能实现的事。
幸运的是，这里海产丰富，岛上的居民可以用海产补给食物。此外，居民偶尔还可以捕到海豹、海象、北极狐、野兔和北极熊等，把它们的皮毛或牙齿做成奢侈品。在北欧市场上，这些奢侈品销路很广，甚至还可以出口到欧洲大陆的中心地带。
殖民工作顺利开展起来了。在流放的三年中，埃里克可能已经给自己选好了以后的住址，他清楚自己要在哪里定居。在几处狭长海湾的源头位置，埃里克建立了自己的农庄，取名为“布莱特列”。这块地方很宜人，因为有“埃里克峡湾”做屏障，北极寒冷的海水正好无法流入，至今格陵兰岛上最优质的农田依然在这里。峡湾中狭长水域和岛屿纵横分布，水草丰美，因此可以饲养家畜；在维京时代，家畜象征着财富。其他人也都散居于埃里克的农庄附近。
富有智慧的维京人有着许多创新发明，例如他们通过灌溉来保护农作物，让作物免于冻害110，正是因为有了这些创新发明，殖民地人口剧增，达4万之多。当时很多人一致同意在距离西北部170英里远的地方建立第二个殖民地。111这样一来，埃里克自然而然就被推选为东部定居点的长老“哥提”。他们在布莱特列建了会堂，岛上的大小事宜都在这里商议决定。
到了夏天，天气相对暖和了，一些殖民者就会驾船向北航行，去近1000英里外的地方猎捕海象、海豹及搁浅在沙滩上的鲸鱼。112这类航行收益颇丰，因此殖民者们甚至愿意为此冒着生命危险，埃里克也因此成了一名富翁。
格陵兰岛上的居民并不常回冰岛或挪威，不过两地之间总有人走动，因此格陵兰岛和其他两地之间仍然保持着联系。当时有移民离开斯堪的纳维亚半岛，打算移居冰岛，却发现冰岛已经拥挤不堪，所以只好来到格陵兰岛，因此总有新的移民者陆续来到岛上；还有一些远在故乡的亲戚来格陵兰岛走访，其间也有些殖民者放弃在格陵兰定居，返回了家乡。
虽然埃里克再也没有离开过格陵兰岛，但他的后代却继承了他当初到处游荡的志向，回了几趟挪威。埃里克同他的妻子肖希尔德（Thjodhildr）至少生有三个儿子，长子名叫莱夫，他曾进行了一次探险，即在999年夏天穿过格陵兰岛回到了挪威。
莱夫为什么要回挪威我们不得而知，不过因为当时他是携妻子一道离开格陵兰岛的，因此我们推测他可能打算在挪威定居。当时莱夫想在国王奥拉夫·特里格维逊手下找一份差事干，最后他做了宫廷侍卫。那时的奥拉夫正急需这样的人才，因为他当时正在挪威强制推行基督教，这一举措引起了很多人的反对；最后这位国王还是没能成功，他在斗争中丢了性命，不过他让一位重要人物转变了自己的信仰，那就是莱夫。大约在999年冬季，莱夫成了基督徒，同妻子一起接受了洗礼。
奥拉夫逝世之前，他要求莱夫以传教士的身份回到格陵兰岛，去那里传播基督教。莱夫同意了奥拉夫的这项提议，但在返航的途中遇上了风暴，船只严重偏离了航向。风暴平息之后，迷雾终于消散，莱夫总算看到了陆地的影子，但让他困惑的是眼前这块陆地草木葱郁，并非自己所找的那块贫瘠不堪、怪石嶙峋的岛屿。莱夫意识到这可能是格陵兰岛以西的某个岛屿，所以他掉转航向，朝着反方向往回航行，殊不知自己已经看到了新世界。
但此刻莱夫关注的只是人死后的“天国”，所以他一回到布莱特列，就立即在东部定居点着手进行让当地人皈依基督教的活动。113莱夫发现这里很多人都渴望成为基督徒，但他自己的成功是以家庭破裂为代价的。当时莱夫的母亲肖希尔德成了一名虔诚的基督徒，但他的父亲“红胡子”埃里克却无法接受这一点，埃里克是名高傲的异教徒。后来肖希尔德在布莱特列建了一座教堂，此后家庭内部矛盾急剧上升，肖希尔德提出除非他摒弃自己的信仰皈依基督教，否则便要和他分居——我们从各类英雄传说中得知，肖希尔德的做法“让埃里克恼羞成怒”。
为了让家人从这场宗教争端中走出来，莱夫做了一项新的决定：西部有一块人类还未发现的陆地，他要去那里探险。莱夫邀请自己的父亲一道前行——埃里克发现格陵兰岛的成功经历已经让他成了好运的象征，但当时这位长老的身体已经每况愈下，所以最终没有跟莱夫一起去。114
莱夫·埃里克松并不是第一个到过美洲的人，这份殊荣当归于比雅尼·何尔约夫森，他是格陵兰岛第二大富豪的儿子。比雅尼的父亲何尔约夫也是最早到达格陵兰岛的移民之一，他在冰岛的时候就与埃里克关系甚密。当时何尔约夫在冰岛过得相当不错，但还是没能说服儿子比雅尼跟他一块到冰岛生活。这可能是因为当时比雅尼在挪威的生意已经做得风生水起，颇为成功，所以比雅尼并不想来到拥挤的冰岛再从头开始自己的事业；然而比雅尼许诺每年都会探望父母一次，似乎后来他也一直在履行自己的承诺。986年，在一年一度的访亲时节比雅尼来到了冰岛，却找不到父亲的影子，有传言称父亲已经离开冰岛去了格陵兰岛。
比雅尼当时立即决定去格陵兰岛寻找父亲，但是他当时面临着相当严峻的航行问题：他自己和其他的冰岛人都不曾去过格陵兰岛，除了往西行驶这个模糊的印象外，根本没有人知道该怎么去那里。他们没有地图，没有指南针，甚至连格陵兰岛是什么样子也没人知道。尽管如此，比雅尼还是领着几个自愿跟他前行的船员出发了，果然不出所料，他们在海上完全迷失了方向，越过了目的地。
比雅尼最先看到的是一块山丘起伏的陆地，那里林木茂密，郁郁葱葱，这说明他到的肯定不是格陵兰岛。对于这些曾到过冰岛又打算去格陵兰岛的人来说，突然见到这么多林木是件稀奇古怪的事情。陆地上到处都是森林，就像一层绿色的地毯绵延不绝，一直从沙滩的边缘延伸到远处起伏的山丘上。这群挪威人把这里称为“马克兰”（Markland），意指“森林之地”，他们并不想留在这里探险，而是继续向北航行。115
接下来他们来到了一块岛上，这里有很多形状古怪的扁平巨石，每块巨石足够两人头脚相连地躺在其上。他们看到的唯一的生物就是北极狐，在船只靠近海岸的时候这些狐狸便飞快地跑开了。维京人管这里叫作“荷鲁兰”（Helluland），意指“扁石之地”。116
这次，比雅尼还是不允许大家去岛上探险，因为他急于找到自己的父母。不过这次他们遇上了顺风，恰逢东风过境，所以仅仅4天之后，他们就到了格陵兰岛。比雅尼终于和父亲团聚了，也许他再也不愿意重走那段艰险的旅途，所以决定长期定居格陵兰岛。他在西部发现新大陆的故事只是引起了人们的好奇，最初却并没有什么人有兴趣去寻找那些陆地。
就连比雅尼自己都把这事搁置下来了，因为他是一名商人，而不是探险家，他所关注的是货物和利润，而不是建立殖民地或跟原住民斗争。后来何尔约夫逝世以后，比雅尼继承了父亲的地产，定居下来靠种地过活。117
10年之后，莱夫·埃里克松声称自己要驾船西行的时候，比雅尼仍然不想跟他同去探险，但他把自己的船只卖给了莱夫，并领着莱夫找到了当年跟着自己航行过的幸存船员——他们当中的大多数都参加了莱夫的探险之旅。当时去探险的总共有35人，但在只有一艘船的情况下，这个数目已经算是很大了。这次探险有两个目的，一是为了寻找合适的殖民地；更为重要的一点是为了寻找原材料。如果新大陆上当真有比雅尼所说的那么多树木的话，那格陵兰岛上所有的资源问题就可以迎刃而解了。那时格陵兰殖民地已经面临着严峻的生存危机，但当时的莱夫并没有意识到这一点。