Ten thousand years before the first age, middle earth was a different place. It was ruled by a dark lord, and it was mostly plains. Na'vi elves appeared around then, and began to build the first ever elven kingdom. It was just known as "The Na'vi kingdom". It was five times the size of Minas Tirith, but much resembled it.
Five thousand years before the first age, early Orcs began to thrive, and decided to take over the Na'vi kingdom. The siege began, and 200,000 orcs came to take over the most powerful kingdom at the time. For six days, the Na'vi elves fought back and chased the Orcs back to early Mordor.
About six thousand years later, Isengard, back then known as Isengardia, which included creatures such as: early trolls, orcs, goblins, made an alliance with Angmar and Mordor and to take over the Na'vi kingdom. 6,000,000 soldiers from Angmar and Mordor attacked and took over the kingdom, killing 4,000,000 Na'vi people, leaving 1,000 only to retreat.
Now living in darkness, the remainding Na'vi people lived in tribes and groups. Soon, Na'vi elves began to evolve into human looking elves, with the normal pale skin instead of blue skin. But 300 Na'vi people refused to evolve, and soon took a spell leaving them blue and as they were.
In the fourth age, Na'vi people stayed in tribes and forests hidden from contact.