Hoewel slechts enkele schepen deelnamen aan de eerste vikingtochten, nam hun aantal steeds meer toe en bestonden de vloten die in westelijke richting naar Engeland, Schotland, Frankrijk en Ierland voeren uit vele honderden schepen. Ze kwamen als rovers en plunderaars en waren een ware verschrikking voor de kusten die ze aandeden. Maar het waren ook handelaars en bestuurders. Ze stichtten steden als Dublin en kolonies als Normandië, in Frankrijk. Van 879 tot 920 koloniseerden ze IJsland, dat vervolgens een uitvalsbasis werd voor de kolonisatie van Groenland.
De in Noorwegen geboren Eirik Thorvaldsson, ook wel Erik de Rode genoemd, ontdekte en koloniseerde in 986 het zuidwestelijke deel van Groenland. Zijn zoon, Leiv Eiriksson, was de eerste Europeaan die voet aan wal zette aan de Noord-Amerikaanse kust. Deze eerste ontdekkingsreiziger van Noorse afkomst geniet nu wereldwijd erkenning.
De geboorteplaats en -datum van Leiv Eiriksson is niet definitief vastgesteld, maar aangenomen wordt dat hij is opgegroeid op Groenland. In de sage van Erik de Rode wordt verteld dat hij in 999 naar Noorwegen voer, een periode in dienst was van koning Olav Trygvasson en een jaar later teruggestuurd werd naar Groenland om de bevolking aldaar het christendom te brengen.
Er bestaan twee versies van de daaropvolgende gebeurtenissen. Een daarvan is dat Eiriksson, op weg naar Groenland, van koers raakte en bij toeval in het jaar 1000 de kust van Noordwest-Amerika bereikte, bijna 500 jaar eerder dan Columbus. Volgens de Groenland-sage, die in het algemeen als betrouwbaar wordt beschouwd, was de ontdekking van Eiriksson echter geen toeval. De sage verhaalt van een expeditie die werd opgezet om in westelijke richting te varen, in een poging bewijs te vinden voor de beweringen van de IJslandse handelaar Bjarni Herjulfsson. In 986 meldde Herjulfsson, flink uit de koers gedreven door een zware storm tussen IJsland en Groenland, dat hij ver in het westen een heuvelachtig, zwaar bebost land had zien liggen. Herjulfsson, waarschijnlijk de eerste Europeaan die een blik wierp op het Noord-Amerikaanse continent, zette er echter nooit voet aan wal. Leiv Eiriksson, aangemoedigd door de geruchten over potentiële ontdekkingen en de constante behoefte aan landbouwgrond, kocht Bjarni's schip en ging op ontdekkingsreis.
Klaarblijkelijk volgde hij Bjarni's route in omgekeerde richting, waarbij hij drie keer land bereikte. Het eerste land noemde hij Helluland, of Vlaksteenland, waarvan men nu vermoedt dat het Labrador geweest moet zijn. Het tweede was Markland, of Bosland, mogelijk Newfoundland. Over de exacte locatie van het derde land, dat Vinland (Weideland) werd genoemd, bestaat in wetenschappelijke kringen nog steeds veel onenigheid, maar het zou zo ver naar het noorden kunnen liggen als Noord-Newfoundland of zo ver naar het zuiden als Cape Cod, en mogelijk nog verder.
Eiriksson en zijn mannen brachten de winter door in Vinland, op een plek die ze Leifsbud-ir noemden, en keerden het jaar daarop, in 1001, terug naar Groenland.
Toen was het de beurt aan de broer van Eiriksson, Thorvald, om een reis naar het pas ontdekte gebied te maken, want Leiv Eiriksson keerde er nooit meer naar terug. Herhaalde pogingen van de vikingen om zich op Vinland te vestigen waren geen succes, omdat er veel wrijving bestond tussen hen en de inheemse Noord-Amerikaanse bevolking.
Hoewel velen Christopher Columbus nog steeds als de ontdekker van de Nieuwe Wereld beschouwen, werd Eirikssons recht op deze titel officieel door de Verenigde Staten erkend toen president Lyndon B. Johnson in 1964, unaniem gesteund door het Congres, 9 oktober uitriep als "Leif Ericson Day", ter herinnering aan de komst van de eerste Europeaan naar Noord-Amerika.