Bár a kezdeti viking kalandozásokban még kevés hajó vett részt, számuk fokozatosan növekedett, így a nyugati part felé, Angliába, Skóciába, Franciaországba és Írországba tartó flották már több száz hajóból álltak. A vikingek rablóként, fosztogatóként érkeztek, félelemben tartották a partmenti lakosságot, de egyúttal kereskedők és államszervezők is voltak. Városokat és gyarmatosító kolóniákat alapítottak, mint például Dublint Írországban és Normandiát Franciaországban. 879 és 920 között kolóniát hoztak létre Izlandon, mely később a Grönlandra áttelepülő vikingek bázisa lett.
986-ban a Norvégiában született Eirik Thorvaldsson, ismertebb nevén Vörös Erik, felfedezte Grönland dél-nyugati részét, ahol viking települést alapított. Fia, Leif Eiriksson volt az első európai, aki partra szállt Észak-Amerikában, ezzel a norvég terjeszkedés első, ma már széles körben elismert felfedezőjévé vált.
Leif Eiriksson születésének pontos idejét és helyét ezidáig még nem sikerült kétséget kizáróan megállapítani, de általános vélekedés szerint Grönlandon nőtt fel. A Vörös Erikről szóló saga beszámol arról, hogy 999-ben Norvégiába hajózott, egy éven át Olav Trygvasson király szolgálatában állt, majd visszaküldték Grönlandra, hogy a sziget lakosságát keresztény hitre térítse.
Az események további alakulását tekintve két történeti iskola létezik. Az egyik szemlélet szerint a Grönland felé tartó Eiriksson hajóját egy hatalmas vihar letérítette eredeti útvonaláról, és a viking hajós véletlenül ért partot az észak-amerikai kontinensen 1000-ben, mintegy 500 évvel megelőzve Kolumbuszt. A hitelesnek tekintett Grönland-saga szerint azonban Eiriksson felfedezése nem csupán a véletlennek köszönhető. A saga elbeszéli, hogy Eiriksson expedíciót szervezett és nyugati irányba hajózott, hogy bizonyítékot szerezzen egy izlandi kereskedő, Bjarni Herjulfsson állításának alátámasztására. 986-ban Herjulfsson óriási viharba került hajójával Izland és Grönland között, és messze sodródva úticéljától hegyes, erdős szárazföldet vélt felfedezni a nyugati horizonton. Feltehetően Herjulfsson volt az első európai, aki megpillantotta az észak-amerikai kontinenst, de partra nem szállt. Leif Eirikssont azonban tettre sarkallta a lehetséges felfedezésről szóló szóbeszéd, valamint az a tény, hogy a grönlandiaknak nagy szükségük volt megművelhető termőföldre, ezért megvásárolta Bjarni hajóját és saját expedíciót indított.
Eiriksson valószínüleg a Bjarni által bejárt útvonalat követte, csak éppen visszafelé, felfedezőútja során háromszor szállt partra. Az elsőként elé táruló tájat Hellulandnak, azaz Kőországnak nevezte el, mely alighanem Labrador lehetett. A második kikötéskor felfedezett földnek a Markland, vagyis Erdőország nevet adta, ez minden bizonnyal a mai Új-Fundland. Harmadjára szőlőben gazdag vidékre érkezett, melyet ezért Vinlandnak, tehát Szőlőországnak keresztelt el. Ennek a helynek a pontos fekvése máig tudományos vita tárgya, lehetett Új-Fundland északi részén, de akár Cape Codtól jóval délebbre is. Eiriksson csapata Vinlandon töltötte a telet egy olyan táborhelyen, melyet vezetőjük után Leifsbudnek neveztek el, majd a következő évben, 1001-ben visszatértek Grönlandra.
Leif Eiriksson soha többé nem tért vissza az újonnan felfedezett földre, így bátyjára, Thorvaldra hárult a feladat, hogy a következő expedíció élére álljon. Vinlandon több egymást követő kísérlet történt egy állandó település létrehozására, de ezek mindegyike kudarcba fulladt a viking telepesek és az őslakosok közötti ellenségeskedés miatt.
Bár sokan még mindig Kolumbusz Kristófot tartják az Újvilág felfedezőjének, Eiriksson jogosultságát erre a titulusra már az Egyesült Államokban is elismerték. Lyndon B. Johnson amerikai elnök 1964-ben a Kongresszus teljes támogatásával jelenthette be, hogy október 9-ét Leif Eiriksson Napjának nyílvánítják, az első európai hajós partraszállásának emlékére.