As always, spoiler warnings...

'I also will come,' said Legolas, 'for I do not fear the Dead.' (Book 5, The Passing of the Grey Company)

Though Elves do not die, they fade in Middle-earth. It appears that a yearning for the Undying Lands is normal, even for Sindar like Legolas. Galadriel predicts Legolas will have that yearning if he so much as hears a gull. 'Beware of the Sea!' (Book 3, The White Rider). And indeed, her prophesy comes true:

And now Legolas fell silent, while the others talked, and he looked out against the sun, and as he gazed he saw white sea-birds beating up the River.   'Look!' he cried. 'Gulls! They are flying far inland. A wonder they are to me and trouble in my heart. Never in my life had I met them, until we came to Pelargir, and there I heard them crying in the air as we rode to the battle of the ships. Then I stood still, forgetting war in the Middle-earth; for their wailing voice spoke to me of the Sea. The Sea! Alas! I have not yet beheld it. But deep in the hearts of all my kindred lies the sea-longing, which it is perilous to stir. Alas! for the gulls. No peace shall I have again under beech or under elm.' (Book 5, The Last Debate)

This is not death, but Legolas clearly feels he has lost something essential to his nature. The peace he always found in the forest has been lost. He calls this longing 'perilous.' He finds himself forgetting his immediate situation and the quest he has been a part of for many months. These are all akin to the foreshadowing of death - a loss of interest in the world one has been immersed in. We can also see a parallel between this and his encounter with the Huorns, where he suffers from a compulsion to go off by himself, forgetting his obligations, leaving his friends.

(Side note: While we can only generally speculate on Legolas' age, he seems rather provincial, particularly as he at least the second-oldest member of the Company. Aragorn and Gandalf are easily the most well-traveled of the Company - even Boromir appears positively 'regional' alongside those two. But we are explicitly told Legolas has never been to Lothlorien and has never before been close enough to the Sea to hear a gull. From all appearances, he has never been to any of the places the Company travels to after leaving Rivendell, and it may well be we meet him during his first visit to the Last Homely House. Relative to his age, Legolas appears to have a Sam Gamgee-level of stay-close-to-homeness prior to this quest.)

As noted in the last section, Elves in general morn the effects the passing of time has on Middle-earth. The LOTR in general is infused with loss, of a past that was greater and is now gone. The main characters come across ruins and travel through empty lands where many people once lived, again and again. 'Alas for us all!' says Legolas as the Company leaves Lorien. 'And for all that walk the world in these after-days. For such is the way of it: to find and lose, as it seems to those whose boat is on the running stream.' (Book 2, Farewell to Lorien). Later: 'The deeds of Men will outlast us, Gimli.' (Book 5, The Last Debate).

Beside calling them 'children,' what are Legolas thoughts on mortals and their mortality? Clearly, the spirits they meet on the Paths of the Dead do not bother him, as noted in the quote above. When the Grey Company enters the Paths, and the narrator tells us that 'The Company halted, and there was not a heart among them that did not quail, unless it were the heart of Legolas of the Elves, for whom the ghosts of Men have no terror' (Book 5, The Passing of the Grey Company). Legolas mentions it again in telling the tale to the hobbits: 'I felt not the horror, and I feared not the shadows of Men, powerless and frail as I deemed them' (Book 5, The Last Debate).

He is not unaffected by death, however. Legolas mourns. On Boromir's passing, he is the one to insist, 'First we must tend the fallen... We cannot leave him lying like carrion among these foul Orcs.' Gimli and Aragorn raise the need to follow the Orcs without delay, but Legolas returns: 'Then let us do first what we must do,' said Legolas. 'We have not the time or the tools to bury our comrade fitly, or to raise a mound over him. A cairn we might build.' (Book 3, The Departure of Boromir). (In their song for Boromir, Legolas appropriately sings the verse about the South Wind, with its references to the sea and gulls, although it is still a while before he will first hear a gull.)

Similarly, he understands the meaning of the song Aragorn sings in the language of the Rohirrim. He notes 'it is like to this land itself; rich and rolling in part, and else hard and stern as the mountains. But I cannot guess what it means, save that is laden with the sadness of Mortal Men' (Book 3, The King of the Golden Hall), which indeed it is. His grief after Gandalf's passing is so great, he refuses to translate the memorial songs sung by the Elves of Lorien because 'that for him the grief was still too near, a matter for tears and not yet for song' (Book 2, The Mirror of Galadriel).

Legolas seems to enjoy his post-LOTR life, traveling with Gimli in the Glittering Caves and Fangorn, and, in the Appendices, we are told he led Elves out of Greenwood to Ithilien, following through on plans he and Gimli made when they first entered Minas Tirith. Even in that moment, however, his sea-longing could not be forgotten:

'In days to come, if my Elven-lord allows, some of our folk shall remove hither; and when we come it shall be blessed, for a while. For a while: a month, a life, a hundred years of Men. But Anduin is near, and Anduin leads down to the Sea. To the Sea!'   ...For our days are ending and our years failing. I will pass the wide waters lonely sailing... In Eressea, in Elvenhome that no man can discover, Where the leaves fall not: land of my people for ever!'   And so singing Legolas went away down the hill. (Book 5, The Field of Cormallen)

Legolas hangs on for another 122 years after the destruction of the ring, 'but when King Elessar gave up his life Legolas followed at last the desire of his heart and sailed over Sea... We have heard tell that Legolas took Gimli Gloin's son with him because of their great friendship, greater than any that has been between Elf and Dwarf' (Appendix A).

Continue on to Part 6...