After the Elves, the Firstborn of Ilúvatar, awoke under the stars at Cuiviénen, they stared at the stars, amazed by them, and by the world they had just come in to. In time they began to talk to one another and, since they had met no other creatures in Middle Earth who could talk, they named themselves the Quendi, or "those who use speech."
There was evil in the world at this time, in the shape of the Valar Melkor and his horrible creatures. He captured those of the Quendi who strayed too far from the larger group, and the Elves, therefore, were frightened of him, or any stranger.
They dwelt by Cuiviénen for quite awhile before any of the other Valar knew they were there. One day, the Valar known as Oromë, the Great Hunter, was riding across Middle Earth on his horse, Nahar, when he suddenly heard the sound of singing far off. The sound led him to Cuiviénen and the Quendi. Needless to say, both he and the group of Elves were each surprised to see the other. Some of the Elves were so frightened that they ran away and were lost, but others were merely wary and gradually came to accept him.
He found them quite lovely and amazing, for Ilúvatar had made them the lovliest creatures in Arda, and Oromë called them the Eldar - the People of the Stars.
In the beginning of Tolkien's mythology, Eldar technically referred to all of those who dwelled at Cuiviénen, but eventually that name would be retained only by those of the Firstborn who chose to make the Great Journey to Valinor. (Note that even if an Elf never actually made it to the Undying Lands, he would be known as one of the Eldar. The name applied to all those who attempted the trip.)
- The brightest stars of the heavens, which the Elves loved so much, were fashioned by Varda, the Queen of Valar, so that they should not dwell in darkness. Because of this, of all the Valar the Elves love Varda the most. In the Sindarin language, which the Elves of Middle Earth used, Vanya's name was Elbereth and those Elves composed a hymn to her called A Elbereth Gilthoniel ("O Elbereth, the Star-Kindler.") Frodo uses this name against the Ringwraiths in The Fellowship of the Ring.