Sagi wspominają, że Eryk Rudy po wygnaniu z Islandii, wypłynął na poszukiwania lądu, który według tradycji miał jako pierwszy ujrzeć Gunnbjörn Ulfsson. Po kilku dniach dotarł do wybrzeży Grenlandii. Opłynął jej południowe brzegi (znane później pod nazwą Farvel) i skierował się wzdłuż zachodniego wybrzeża. W końcu dopłynął w okolice, których większą część pokrywał lód. Według Sagi o Eryku Rudym spędził tam trzy lata na eksploracji. Pierwszą zimę spędził na wyspie Eiriksey, drugą w Eiriksholmar (niedaleko Hvarfsgnipa), a ostatnie lato poświęcił na eksploracje dalekiej północy (Snaefell i Hrafnsfjord).
Kiedy trzyletnie wygnanie dobiegło końca Eryk powrócił na Islandię, by opowiedzieć o swojej podróży. Nową ziemię nazwał „Grenlandią” (czyli zieloną ziemią), żeby przyciągnąć do niej potencjalnych osadników. Uważał, że ludzie będą bardziej skłonni się tam osiedlić, jeżeli jej nazwa będzie zachęcająca. Po przezimowaniu na Islandii, zebrał dużą grupę kolonistów i powrócił na Grenlandię, gdzie na południowym zachodzie wyspy założył dwie kolonię: Osiedle Wschodnie oraz Zachodnie. Powstało też Osiedle Środkowe, ale przypuszczalnie było ono częścią zachodniej osady.