Premières observations. En 986 après JC, Bjarni Herjolfsson était en route pour le Groenland depuis l'Islande lorsque lui et son navire se sont perdus dans une tempête. Une fois le ciel dégagé, il vit «un pays qui n'était pas montagneux, mais bien boisé et avec de basses collines. . . . » Ainsi fut faite la première observation européenne enregistrée d'Amérique du Nord. En tant que nouveaux arrivants au Groenland, les Scandinaves n'étaient guère préparés à s'étendre à nouveau vers l'ouest, et ce n'est qu'après que la population a augmenté et que les terres se sont raréfiées que les Vikings ont commencé à calculer les avantages de la colonisation des terres qu'Herjolfsson avait repérées. En 1001, Leif Ericsson acheta le navire d'Herjolfsson, l'équipa avec une partie de l'équipage de l'ancien propriétaire et rechercha la mystérieuse terre de l'ouest qu'ils appelaient Vinland, où ils construisirent une petite colonie appelée Leifsburthir.
Premier contact. Après le retour d'Ericsson et de ses hommes au Groenland, Thorvald Ericsson partit en 1006 pour Leifsburthir. Sur la plage, ils ont vu trois bosses qui, après une inspection plus approfondie, se sont révélées être des bateaux en peau sous lesquels dormaient plusieurs Indiens. Thorvald a tué huit des hommes effrayés, et son équipage s'est replié sur leur navire. À leur grande surprise, des dizaines de bateaux en peau remplis d'Indiens sont apparus au large, et les Vikings ont pris une position défensive. Les soi-disant Skraelings lâchèrent plusieurs barrages de flèches, dont l'une frappa Thorvald à mort. Après que les Indiens se soient retirés, les membres d'équipage restants ont enterré leur chef à proximité et se sont enfermés à Leifsburthir pour l'hiver. Au printemps, ils ramassèrent du bois, récoltèrent quelques raisins et retournèrent au Groenland avec une image moins rose du Nouveau Monde.
La colonie du Vinland. Trois ans plus tard, Thorfinn Karlesefni, sa femme et 160 autres colons ont localisé Leifsburthir, réparé les maisons délabrées et construit plusieurs nouveaux bâtiments pour abriter le reste des colons. Les relations ultérieures avec la population locale, cependant, ont convaincu Karlesefni qu'ils étaient non seulement plus nombreux que les Vikings, mais avaient également le potentiel de détruire la petite colonie.
Guerre avec les Skraelings. Les habitants indigènes ont été intrigués par le bétail que les Vikings avaient amené avec eux et ont limité leurs premiers échanges de marchandises à des fourrures et des peaux contre du lait frais. Plus tard, ils ont ajouté du tissu rouge à la liste des produits qu'ils désiraient, et ils étaient toujours intrigués par les armes métalliques des Vikings. Lors d'une visite commerciale dans la colonie, un indigène a tenté de s'emparer d'une épée et son propriétaire l'a immédiatement tué. Le reste de ses compagnons s'est enfui et Karlesefni a averti ses hommes de se préparer à une bataille. Des semaines plus tard, l'assaut est arrivé. N'eut été de l'héroïsme de Freydis, la demi-soeur de Leif, qui fonça tête baissée sur les assaillants, les Vikings auraient été vaincus. Après avoir passé trois hivers au Vinland, Karlesefni et les colons se replient au Groenland. Freydis a fait un voyage ultérieur au Vinland, mais l'échec de Karlesefni a mis fin à la tentative de colonisation de la région. En 1014, un contact soutenu entre le Groenland et le Vinland s'était arrêté, mais au cours des siècles suivants, un navire occasionnel a été éjecté de sa route dans les eaux empruntées pour la première fois par Herjolfsson.