De var bare noen få vikinger som deltok til å begynne med, men gradvis vokste flåten, og til slutt drog hundrevis av stolte langskip i Vesterled – mot England, Skottland, Frankrike og Irland. Vikingene kom som røvere for å plyndre og drepe, og det sies at deres ry etter hvert skapte frykt langs alle Europas kyster. Deres ettermæle er imidlertid ikke helt rettferdig; de var drevne handelsmenn og administratorer også. Mange steder grunnla de byer – som for eksempel Dublin, eller kolonier – som Normandie i Frankrike. I perioden mellom 879 og 920 koloniserte de Island, som i sin tur var utgangspunktet for kolonialiseringen av Grønland.
I 986 drog norskfødte Eirik Thorvaldsson – bedre kjent for ettertiden som Eirik Raude – til Grønland og utforsket den sør-vestre delen, før han besluttet å slå seg ned på øya. Sønnen til Eirik Raude, Leiv Eiriksson ble den første europeer som satte føttene på nordamerikansk jord. Dermed ble han også den første nordmannen som er tildelt plass blant de store oppdagelsesreisende.
Tid og sted for Leiv Eirikssons fødsel er aldri fastslått med sikkerhet. Det er imidlertid dokumentert at han vokste opp på Grønland. Eirik Raudes Saga beretter at han satte seil mot Norge i 999, hvor han gikk i kongens, Olav Trygvassons, tjeneste. Ett år senere ble han sendt tilbake til Grønland for å bringe kristendommen til folkene som hadde bosatt seg der sammen med Eirik Raude.
Det som så skjedde hersker det delte meninger om. Noen hevder at Leiv Eiriksson ble drevet ut av kurs på turen tilbake til Grønland, og at han ved et tilfelle fikk landkjenning med den nord-østligste delen av det nordamerikanske kontinentet. Dette skjedde i år 1000, altså nesten 500 år før italieneren Columbus «gjenoppdaget» Amerika.
Ifølge en annen versjon som baserer seg på Grønlandssagaen, en beretning man vanligvis oppfatter som etterrettelig, var Leiv Eirikssons oppdagelse av Amerika slett ingen tilfeldighet. Sagaen forteller at Leiv utrustet en ekspedisjon med sikte på å få bekreftet den islandske handelsmannen Bjarni Herjulfssons beretning om et land med skogbevokste åser langt i vest. Herjulfsson hadde drevet ut av kurs i en voldsom storm underveis mellom Island og Grønland i 986. Antagelig er han den aller første europeer som fikk et glimt av det nye kontinentet, men han satte aldri foten på land. Etter hjemkomsten kjøpte Leiv Eiriksson skipet til Herjulfsson, og la ut på sin senere så berømte oppdagelsesferd.
Det første stedet Leiv Eiriksson gikk i land kalte han Helluland – Landet med de mange flate hellene – nå alminnelig anerkjent som Baffin Island. Det neste stedet kalte han Markland eller Skoglandet, antagelig det vi nå kaller Labrador. Den nøyaktige lokaliseringen av den tredje landkjenningen, Vinland, strides imidlertid de lærde om. Det er ingenting i veien for at det kunne ha vært så langt nord som den nordligste delen av Newfoundland, eller så langt sør som Cape Cod, eller enda lengre sør, for den saks skyld!
Leiv Eiriksson og karene hans overvintret i Vinland, på et sted de kalte Leifsbudir, og drog hjem til Grønland året etter, i 1001.
Det skulle bli Leivs bror Thorvald, som sto for den neste ferden til det nyoppdagede landet, for så underlig det enn kan virke, ble det aldri til at Leiv vendte tilbake. En rekke forsøk på å opprette en nybyggerkoloni i Vinland slo feil, ikke minst på grunn av de sterke motsetningene mellom de norske nybyggerne og lokalbefolkningen – skrælingene – antagelig de nordamerikanske indianerne eller eskimoene (inuitene).
Til tross for at mange fremdeles betrakter Christopher Columbus som den nye verdens oppdager, har Leiv Eirikssons hevd på tittelen fått offisiell godkjennelse, i bl.a. USA. I 1964 erklæte den amerikanske presidenten, Lyndon B. Johnson – med tilslutning fra en samlet Kongress – den 9. oktober som «Leif Ericson's Day», til minne om den første europeer som satte sin fot på amerikansk jord.