Executive Meddling: The game was originally supposed to be an expansion to OoT, titled "Ura Zelda". However, when the designers expressed displeasure with this idea, they were challenged to make a new adventure in 1 year.
Fandom Nod: The infamous Child Link Statue made famous by Ben Drowned makes a cameo in the debut trailer for the 3DS remake.
Early screenshots showed the moon to have no face.
The game began development for the N64 add-on called the 64DD (or the "Nintendo 64 Disk Drive"), and was going to make use of some of the add-on's features. The game would have used a real time clock instead of the in game one, and was going to use a full 7 day week instead of three days like the final game, but these were dropped from the final product since there were difficulties trying to get these features to work on standard N64 hardware (even with the required RAM expansion pak). There was also a proposed feature regarding being able to "buy extra time" from a merchant who... sold time, but the change to the clock system and lessening of days made the merchant seem less important.
Instead of the Fierce Deity's Mask, there was going to be a mask in the game that would have let Link turn into his adult self from Ocarina of Time (evidence of its existence can be seen in really early screenshots). This mask was scrapped for being mostly useless since all major equipment could be used by young Link this time around. Not wanting to let the "adult Link" aspect go to waste, however, the developers put in the Fierce Deity's Mask instead as a 100% completion bonus that's required to use on the final boss in order to see the Golden Ending. Remnants of this idea include the fact that Fierce Deity Link reuses adult Link's voice clips and model (not textures), as well as an unused mask depicting Link's regular face.
Early screenshots also display various changes to textures throughout the game. A small example is that the Deku Pipes originally were colored white instead of brown, but a much bigger example is some of the wall textures for both inside and outside of Clock Town. The textures originally were a bit more surreal with weird-looking suns, but in the final game the walls textures instead got somewhat less surreal looking designs. Perhaps another very interesting change is that Link was originally going to have the Kokiri Shield from Ocarina of Time return in place of the Heroes Shield (or perhaps as an alternate starting shield), and the Kokiri Sword originally looked exactly like how it did in Ocarina.
Originally, separate icons were used in the HUD for each of Link's instruments (which change depending on which form he's in). The final game just used the Ocarina icon. This idea would be revisited for the 3DS remake, which did have separate icons for each instrument.
Early screenshots showed the Megaton Hammer (or something like it) as Goron Link's weapon. This was replaced by a simple punch for the final game.
One image taken from the earliest stages of development showed that all three Gorman Brothers were originally just one Ingo, and might've worked for Cremia at one point instead of having competition against her.
Before release, the game contained something called the Inspector's Mask, and you were to receive it from Mr. Toto. This mask did not make it into the finished game, and what it would have done remains unknown; however, considering Mr. Toto is familiar with Kafei's mother, and that Kafei's mask allows you to ask people where he's been, it could just have been an earlier version of that.