The son of Thranduil, and so a prince of the Woodland Realm in the northeast of Mirkwood, Legolas was descended from the Sindar, but counted himself one of the Silvan people. The date of his birth is not known, but he seems to have been several thousand years old at the time of the War of the Ring2. Of his life before the end of the Third Age, we know almost nothing. During Bilbo's adventures on his journey to Erebor, he spent several weeks in Thranduil's halls, and later encountered the entire army of the Wood-elves. It seems more than likely, then, that he would have encountered Legolas at this time, but if the two ever met, the fact is nowhere recorded.
After journeying through Rohan, Aragorn elected to take the Paths of the Dead, and Legolas accompanied him, along with a company now swollen with Dúnedain out of the north and the sons of Elrond. With this Grey Company, Legolas travelled through the darkness beneath the White Mountains, where Aragorn made alliance with the Shadow Host, and then on through the southern lands of Gondor to Pelargir. There, Legolas fought alongside the Dead Men as they captured a Corsair fleet. In that battle he first heard the crying of gulls, and it awoke the sea-longing, filling him with the desire to take ship into the West.
During the War of the Ring, Legolas had formed a great friendship with Gimli the Dwarf, a remarkable thing between two races that normally held profound mistrust for one another. After the War, they journeyed together, visiting Aglarond and Fangorn Forest before travelling to their homes in the north. Soon, though, Legolas and Gimli returned into the south with many of their kindred. Legolas and his Elves of Mirkwood settled in the land of Ithilien, and it came to be called the fairest of all the western lands.
At least, Legolas seems to refer to himself as a Silvan Elf: in Eregion, he says '...the Elves of this land were of a race strange to us of the silvan folk...' (The Fellowship of the Ring II 3, The Ring Goes South). This is confusing, because his father Thranduil is elsewhere identified as one of the Sindar. Tolkien touches on this question in his Letters, where he describes Legolas as '...a Woodland Elf, though one of royal and originallySindarin line.' (The Letters of J.R.R. Tolkien No 297, dated 1967, our italics). The explanation for this is found in the History of Galadriel and Celeborn (in Unfinished Tales), where there's a brief account of the arrival of Thranduil's father Oropher among the Silvan Elves of Greenwood the Great. It's made obvious there that Oropher and his small band of Sindar merged themselves completely with the Silvan people of the Wood, leaving behind their Sindarin inheritance. That's why Oropher's grandson Legolas thinks of himself as a Silvan Elf, rather than one of the Sindar.
Though Legolas' age is never established with certainty, he hints several times that he has lived for a very long time indeed. For example, pondering the building of Meduseld in Edoras, he said 'Five hundred times have the red leaves fallen in Mirkwood in my home since then ... and but a little while does that seem to us' (The Two Towers III 6, The King of the Golden Hall). If he really sees five hundred years as 'a little while', then he would appear to be several thousand years old.
Circumstantial evidence suggests that he was probably born sometime during the Second Age. We know from The Tale of Years that his father, Thranduil, passed into the east of Middle-earth from Lindon in the first millennium of the Second Age. However, this account doesn't mention Legolas his son, strongly suggesting that he had not been born at that point. The fact that Legolas saw himself as one of the Silvan Elves also supports this idea, as his father had not settled among the Silvan people at that time. Most likely, then, he was born after Thranduil had settled in Mirkwood, presumably in the latter part of the Second Age. Roughly speaking, this would make him somewhere between 3,000 and 5,500 years old during the War of the Ring.
It must be admitted that this reasoning is based on indefinite evidence, and it is not impossible that Legolas was much older still. Indeed, there is a mention of an Elf named 'Legolas' in the earliest account of the Fall of Gondolin. This is almost certainly not the same character as Legolas of Mirkwood, but it is not beyond the bounds of possibility that Legolas' life stretched back even into the First Age.