Norjalaiset viikingit eivät Grönlantiin tullessaan tavanneet siellä asukkaita, mutta he tapasivat asumuksien pohjia, kiviaseita ja nahkaveneitten jäännöksiä, jotka osottivat siellä asuneen heille tuntematonta kansaa. Nämä asukkaat luultavasti olivat peräytyneet pohjoista kohti.
Pian he huomasivat välttämättömäksi päästä yhteyteen emämaan Norjan kanssa, jos mieli siirtokunnan menestyä. Eerikin poika Leif suoritti onnellisesti rohkean matkan valtameren poikki ja saapui Norjaan v. 999, ruveten kuningas Olavi Tryggvenpojan asemieheksi. Käännyttyään kristinuskoon hän v. 1000 lähetettiin palaamaan uuteen kotimaahansa, saatuaan kuninkaalta toimekseen käännyttää sekin kristinuskoon. Kun Eerikki Punainen vihdoin siihen suostui, niin se tapahtuikin. Islantilaisten ja Norjalaisten tiedot Grönlannin vanhain siirtokuntain vaiheista ovat kuitenkin hyvin vaillinaiset ja ristiriitaiset ja pelkkää taruakin on seassa paljon; mutta niiden tosipohja ei ole epäiltävissä. On säilynyt sekä raunioita että riimukirjotuksia. V. 1824 löydettiin Upernivikin kohdalta pieneltä saarelta riimukivi, joka osottaa heidän ulottaneen pyyntiretkiään siirtokunnistaan vielä kauemmaksikin pohjoiseen päin: »Erling Sigvathson ja Bjarni Thordarson ja Endride Oddson pystyttivät tämän merkin ja lähtivät pois lauantaina ennen pääsiäisviikkoa.» Monta sataa vuotta kului, ennenkun europpalainen sen jälkeen kävi samoilla paikoilla.
Kertomukset Viinimaamatkoista ovat niinikään ristiriitaiset ja myöhempien lisäysten kautta osasta vieraantuneetkin oikeasta pohjastaan, mutta niitten yhtäpitäväisyys suurien luonnonseikkain kanssa on kuitenkin niin ilmeinen ja sattuva, ettei voi olla vähintäkään epäilystä siitä, etteivätkö norjalaiset viikingit olisi Grönlannista käsin löytäneet Pohjois-Amerikkaa ja tehneet sinne useita retkiä.
Kertomukset Grönlannin eteläpuolella olevien maitten löytämisestä ovat säilyneet kahdessa islantilaisessa sadussa. Toinen näistä, »Eerikki Punaisen satu», on vanhempi ja yleisen luulon mukaan luotettavampikin. Se lienee muistoon kirjotettu vuosien 1270 ja 1380 välillä. Toinen on Islannin pohjoisrannalla syntynyt »Flateyarbok», joka lienee kirjotettu v:n 1387 vaiheilla. Nämä sadut eroavat koko joukon toisistaan. Edellisessä kerrotaan vaan kahdesta Viinimaan matkasta, jälkimäisessä taas viidestä. Edellisen mukaan oli Leif Amerikan ensimäinen löytäjä, jälkimäisen mukaan Bjarni. Vaikka Flateyarbok sisältääkin paljon tarupiirteitä ja on sekavampi, niin ei sitä kuitenkaan voi pitää arvottomana, vaan täytyy meidän koettaa molempien satujen mukaan muodostaa kuva näistä merkillisistä merimatkoista.
»Flateyarbokin» mukaan tapahtui Amerikan löytö seuraavalla tavalla:
Amerikan löytö.
V. 989 eräs Bjarni Herjulfson, seuratessaan isäänsä Islannista Eerikin vuonoon Grönlantiin, joutui myrskyn ajelemana kauas länteen ensin lakealle metsäiselle rannalle ja sitten saareen, joka oli täynnään jäätiköitä. Mutta sitten hän sai hyvän tuulen paremmalta puolelta ja tuli sillä neljässä päivässä kotia Eerikin vuonoon.
Bjarnin löytö herätti suurta huomiota noina Pohjolan varhaisina siirtolaisaikoina, varsinkin kun kuultiin tuossa maassa olevan puita. Norjassa, jonne Bjarni sitten matkusti, häntä moitittiin leväperäisyydestä, kun hän oli jättänyt tutkimatta löytämänsä maan. Kun hän palasi takaisin Grönlantiin, niin »puhuttiin siellä paljon siitä, että piti lähdettämän etsimään tuota uutta maata». V. 1000 Eerik Punaisen poika Leif lähti nimenomaiselle löytöretkelle. Hän osti Bjarnin laivan, otti siihen viisikolmatta miestä ja lähti matkaan. Ensin tultiin siihen maahan, jonka Bjarni oli viimeiseksi nähnyt ja mentiin maihin. Siellä ei ollut ensinkään ruohoa, vaan suuria lumen peittämiä vuorenselänteitä maan sisässä, »ja koko matka rannalta näille vuorille oli yhtä samaa kivikenttää, ja heistä näytti, että se oli vallan hyödytön maa». Ja sen vuoksi he lähtivät pois ja nimittivät seudun Hellulandiksi, s.o. Kivimaaksi, — se luultavasti oli joku kohta Labradorin rannikkoa.
He lähtivät sitten uudelleen merelle ja löysivät toisen maan, joka oli lakea ja metsäinen, edessään valkoinen mereen kallistuva hiekkaranta. »Tämän maan me luontonsa mukaan nimitämme Markmaaksi, s o. Metsämaaksi», sanoi Leif. Purjehtien sieltä kaksi päivää koillistuulella he saapuivat saareen, johon astuivat maihin odottamaan hyvää tuulta. He maistoivat ruohon kastetta, eivätkä mielestään olleet koskaan maistaneet mitään niin makeata. Sitten he purjehtivat edelleen salmeen, joka oli tämän saaren ja erään niemen välissä ja saapuivat paikkaan, jossa järvestä laski mereen virta. He vetivät purtensa järveen ja laskivat ankkurin, kantaen vuoteensa maihin, rakensivat majan ja pystyttivät telttansa sen ympärille, sekä valmistautuivat olemaan siinä talvea.
Kalaruoasta ei ollut puutetta, sillä järvessä oli »suurimpia lohia, mitä he olivat milloinkaan nähneet», ja maa heistä näytti niin hyvältä, ettei siinä tarvinnut talvella ruokkia karjoja. Pakkasta ei ollut ensinkään. Ruoho näytti pysyvän tuoreena vuoden umpeensa ja yö ja päivä olivat taas pitemmät kuin Islannissa ja Grönlannissa. Väki jaettiin kahteen osastoon, toinen puoli rakensi majoja ja toinen tutki maata, palaten joka yö leiriin. Metsäviiniköynnöksestä, jota rehun etsijät löysivät, koko seutu nimitettiin Viinimaaksi, ja niistä otettiin näytteitä niin paljon kuin peräveneeseen mahtui, ja puuta niinikään, ja »itse kylväytynyttä vehnää», jota kasvoi nurmikoilla, koottiin niinikään vietäväksi kotia Eerikin vuonoon. Leif sai nimen »Onnellinen» ja paljon mainetta ja rikkautta, mutta hänen veljensä Thorvald Eerikinpoika arveli, ettei hän ollut riittävästi etsinyt, ja »päätti, että hänestä puhuttaisiin vielä enemmän kuin Viinimaan ensimäisestä asukkaasta».