Navi was first seen in Zelda64 during a mid development between from the very beginning of Zelda64's development to the change over to OOT. Navi has been seen in an array of colours, from magenta, white, green yellow, black, and blue. Eventually after a while in development, Navi began to keep a very similar colour pattern and begin to change the colour depending on her actions, like hovering over signs,npc's or enemies. The Z-targeting system to accompany Navi wasn't introduced til the prerelease period of Zelda's development. The system shared a similar connection to Starfox 64's lock on system in which it has been rumored that is where it originally came from just modified to fit OOT, providing a dynamic camera view while fighting an enemy.
At the beginning of the game, in the depths of Kokiri Forest, the Great Deku Tree, sensing a looming power that threatens to destroy Hyrule, asks one of his fairy children, Navi to take a young boy named Link to see him. Unlike the rest of the inhabitants of the forest, Link does not have a guardian fairy companion. Navi arrives in Link's House, and is surprised to see what a small child Link is, and she has little belief that he has the power to save Hyrule from the powers of evil. Despite this, she tells Link about the Great Deku Tree's summoning, and together, they travel to the grove of the wise tree. The Great Deku Tree tells the two about a curse placed on him by an outsider, and asks them to travel inside him to break the curse. They indeed dispel the curse by defeating Queen Gohma; however, the Great Deku Tree reveals that he was fated to die no matter what the outcome of their excursion into his insides would be. The Great Deku Tree explains that he was cursed by the Gerudo mystic Ganondorf, whom had been seeking the Spiritual Stones; magical stones that have the power to open the door to the Sacred Realm, where the omniscient Triforce can be found. He asks them to stop Ganondorf from achieving this at all costs, and after presenting them with the Kokiri's Emerald, tells them to travel to Hyrule Castle and converse with Princess Zelda, who resides there. From this point, Navi and Link work together to prevent this disaster. While initially, Navi seems to have a general disliking for Link, they eventually grow fond of each other during their quest. After many ordeals, Link and Navi confront Ganondorf at the very top of Ganon's Castle. Ganondorf uses a spell that prevents Navi from helping Link in the ensuing battle. Despite this, Link defeats Ganondorf, who uses his final strength to try and bring the castle down. Link and Zelda narrowly escape, and the tower collapses in on itself. As they celebrate their victory, they hear a slight rumble from the direction of the ruins. Link surveys the scene, and Ganondorf rises from the rubble, utilizing the true power of the Triforce of Power to transform into a monstrous, pig-like beast. Navi promises Link that she will not be held back by Ganondorf again, and together, they defeat the beast and seal it away. Even though Ganondorf is defeated and peace is restored, in the ending, Navi is seen departing from Hyrule in the Temple of Time, where she soars towards the lit window and is never seen again. The reason for her departure is never ascertained.