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 Ring.2 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 the division of the Fellowship, Legolas travelled with Aragorn and Gimli in their chase across Rohan in search of Merry and Pippin. Eventually their trail led them to Fangorn Forest (which enchanted Legolas to the extent that he would later revisit it with Gimli after the War). There, they discovered that the Hobbits were safe, and that Gandalf had returned as Gandalf the White. The Wizard led them to Edoras to meet with Théoden, whom he cured of Saruman's baleful influence. For a time after this, Legolas fought alongside the Men of Rohan. At the Battle of the Hornburg, he slew at least thirty-nine of the enemy, by his own count.
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.
Legolas remained in Ithilien until the death of Aragorn in IV 120. At that time, he gave in to the Sea-longing that had awoken long beforehand at Pelargir, and sailed out into the Great Sea and away from Middle-earth. Legend tells that he took his great friend Gimli with him into the West.
Notes
1
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.
2
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.