Po wygnaniu z Islandii postanowił odszukać ląd wspomniany przez Ulfssona. W tym kontekście, kiedy około 982 roku wypływał w kierunku Grenlandii, była to ziemia nieco tajemnicza i mało znana. Po dotarciu do wyspy opłynął jej południowe brzegi (znane później pod nazwą przylądka Farvel) i skierował się wzdłuż zachodniego wybrzeża. W końcu dotarł w okolice, których większą część pokrywał lód. Według Sagi o Eryku Rudym spędził tam trzy lata na badaniach. 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ę, gdzie opowiedział o swojej podróży. Nową ziemię nazwał „Grenlandią” (czyli zieloną ziemią), żeby przyciągnąć do niej potencjalnych osadników. Wyjaśnił, ż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. Na czele 25 okrętów wyruszył na Grenlandię. Tylko 14 dotarło do celu, a 11 zaginęło na morzu.
Na południowym zachodzie wyspy założył dwie kolonie: Osiedle Wschodnie oraz Zachodnie.