La langue Na'vi tire ses origines du premier travail de James Cameron sur Avatar. En 2005, alors que le film était toujours à l'état de script, Cameron estima qu'il avait besoin d'une langue complète, cohérente pour les personnages qui allaient la parler. Il écrit environ trente mots de cette langue étrangère, mais voulait qu'un linguiste crée la langue dans son ensemble. Sa société de production, Lightstorm Entertainment, entra en contact avec le département de linguistique de l'Université de la Californie du Sud, cherchant quelqu'un qui serait intéressé par la création d'une telle langue. Edward Finegan, un professeur de linguistique à l'USC, conseilla Paul Frommer, avec qui il lui avait cosigné un manuel de linguistique. Frommer et Cameron se rencontrèrent pour discuter de la langue et de son utilisation dans le film.
En se basant sur la première liste de mots de Cameron, qui avaient, selon Frommer, "une consonnance Polynésienne", le linguiste développa trois jeux de mots différents et les expressions montrant à quoi une langue extraterrestre pourrait ressembler : un jeu d'une langue à tons, un jeu avec une quantité vocalique variable et un jeu utilisant les consonne éjectives. Des trois, Cameron préféra le jeu avec les consonnes éjectives. Son choix établit la phonologie que Frommer utilisa dans le reste du développement de la langue Na'vi (la morphologie, la syntaxe et un vocabulaire primitif) ,une tâche qui prit six mois.
La langue Na'vi a été développée avec trois contraintes significatives. D'abord, Cameron voulait que la langue semble étrangère, mais agréable et attirante pour le spectateur. Deuxièmement, puisque le scénario incluait des gens qui apprenaient à parler la langue, cela devait être une langue que les gens pourraient apprendre à parler. Et finalement, les acteurs devraient être capables de prononcer leur dialogue en Na'vi sans de grandes difficultés. La langue en sa forme finale contient beaucoup d'éléments rares dans les langages humaines, comme l'utilisation de conjugaisons verbales insérées (conjugaison verbale utilisant des infixes). Tous les éléments linguistiques na'vi se trouvent dans des langues humaines mais leur combinaison est unique.
Le vocabulaire na'vi fut créé par Frommer pour les besoins du script. Lorsque le casting pour Avatar commença, la langue était suffisamment développée et les acteurs furent incités à lire et prononcer des dialogues en na'vi durant les auditions. Pendant le tournage, Frommer travailla avec les acteurs, les aidant à comprendre leurs dialogues en na'vi et les conseillant sur la prononciation et l'intonation. Les acteurs firent parfois des erreurs en parlant le na'vi. Dans certains cas, ces erreurs trouvèrent une explication plausible selon laquelle leur personnage aurait également fait cette erreur ; dans d'autres cas, ces erreurs furent intégrées dans la langue.
Frommer étendit le vocabulaire davantage en mai 2009 lorsqu'il travailla sur le jeu vidéo Avatar, qui requis des mots en na'vi qui n'avaient pas été nécessaires pour le script du film et n'avaient donc pas été encore inventés. Frommer traduisit également en na'vi quatre ensembles de musiques lyriques qui avaient été écrites par Cameron en anglais et il aida les chanteurs avec leur prononciation pendant l'enregistrement de la bande-originale d'Avatar de James Horner. Au moment où le film est diffusé, le 18 décembre 2009, le vocabulaire na'vi comporte approximativement 1000 mots.
Le travail sur la langue na'vi a continué même après la diffusion du film. Frommer est en train de travailler sur un abrégé qu'il prévoit de rendre à la 20th Century Fox prochainement. Il espère que la langue "aura sa propre vie" et pense que ce serait "merveilleux" si elle en développait une autre.