Spring of Arda
When Varda created the stars in menel, the Elves awoke far in the east, in Cuiviénen, a bay in the Inland Sea of Helcar.
At this time also, Melian wanted to look upon the stars from Taniquetil, saw Middle-earth and desired it.
The following years the Elves (Minyar, Tatyar and Nelyar) long dwelt by the water under stars in wonder and began to make speech, Primitive Elvish, the mother of their languages, naming themselves the Kwendî "those that speak with voices" since they knew no other eloquent things. However they were harassed and captured by spies of the Enemy who took them to Utumno to the North. They were already scared when Oromë riding Nahar found them in awe.
After the Valar made a Battle on the Enemy and destroyed his fortress, so that the Children of Ilúvatar live in safety an comfort, Orome took three ambassadors to Valinor, Ingwë, Finwë and Elwë. When they returned, they invited the other Elves.
Then befell the first sundering of the Elves. The Minyar and most of the Tatyar were swayed by Orome and decided to follow him. The kindreds of Morwë and Nurwë were Unwilling and refused the summons, preferring the starlight and the wide spaces of the Earth to the rumour of the Valar.
The Eldar begun the Great March in three hosts. The Minyar were always the most eager for the road. Next the Tatyar, a greater host and then the Nelyar, the least eager, with two lords: Elwë and his brother Olwë.
As they passed by the Sea of Helcar westwards, they saw great clouds hung still black in the North above the ruins of war. Many of them were scared and turned back.
The journey went slow for the Eldar since Orome frequently departed and then returned to continue the journey. The Eldar were both amazed and tarrying for the nature, and also afraid. Not before after ten Valian years (or a century of coranari) passed, they traversed Greenwood the Great and reached the Great River that would be called Anduin, before the Misty Mountains.
When the first two folk already passed the mountains, the Teleri were still by its eastern banks. Terrified by the tall and dangerous peaks, some of the folk of Olwe refused to continue and stayed there. Their leader was Dân and they became known as Nandor.
The journey continued in greater pace since by another 10 years, while the Teleri must still have been in Eriador, the Vanyar and Noldor came at length over the Blue Mountains and entered Beleriand. The foremost companies passed over the Vales of Sirion and came to the shores of the Great Sea but still, some Eldar were terrified and withdrew into the woods.
That year Oromë returned to Valinor to seek the counsel of Manwë and left the Eldar alone.
By that time, the Teleri came at last to Beleriand and dwelt in the eastward region beyond the River Gelion.
It's possible that by that time, Denethor and some of the Nandor decide to continue the journey after all, and head for the West.
Ulmo comes and using an island as a ship, takes the Vanyar and the Noldor on it to Valinor, while the Teleri still linger. Some of them were looking for Elwe, who fell in a trance after seeing Melian.
Olwe takes those eager to continue the journey and stay near the sea waiting for Ulmo. In the meantime they are befriended by Osse and Uinen and start to love the sea.