Once Upon a Time is the 35th episode of The New Adventures of He-Man.
The episode begins with He-Man, sleeping beneath a tree, tossing and turning in his sleep, he wakes, saying to himself he has had another nightmare. He-Man speaks to the Sorceress, telling her he would like to go home to visit his friends and family, who he misses terribly, but the Sorceress tells him this is not possible as Primus needs him.
Meanwhile, an excited Skeletor tells Flogg, BH and Quakke of his recent acquisition of a spell book called the Encyclopedia of Evil, unfortunately, Skeletor only has one volume of the book, and he wants the entire collection, which is hidden somewhere on Primus. Skeletor gives a brief history of the Tri-Solar Galaxy itself. He tells Flogg the origin of Moon Nordor, that it was once a part of Primus, a fact which disgusts Flogg. When Nordor separated from Primus, only one part of the Encyclopedia remained on Nordor. The books are in a place called ‘The Vaults of Zaktus’. Skeletor has a look to see if there’s a chant to get rid of a Mutant, and ends up reciting an incantation which lifts Flogg into the air and leaves him upside down, much to everyone’s amusement.
The Primans are having a picnic in one of Grot’s gardens, and he leaves to find some fruit for them just as Skeletor discovers the chant to transport himself and the Mutants to Primus. Remaining calm and cheerful as usual, Skeletor asks a shocked Grot if they are in the Oasis, then uses a spell to trap Grot in vines.
Meanwhile, Master Sebrian tells the Inner Council via video link that he has sensed a new evil, and he is suddenly interrupted by Skeletor, who tells him once he finds the other books he’s going to destroy Sebrian and his council.
Meanwhile, Mara and Adam are searching for Grot when an arm reaches through the garden plants and grabs Mara, Adam quickly transforms into He-Man and gives chase, eventually meeting up with BH. He-Man bests BH, tying him up in a vine after a fight. He-Man tells BH to tell Flogg that his Mutants aren’t welcome on Primus, and receives his answer from Skeletor, who has just appeared, ‘Why not tell him yourself?’.
Flogg is still hanging upside down, but is still firing his weapon at He-Man. As He-Man realizes he is outnumbered, a strange glowing light appears as the sky darkens and lightning strikes near them. A strange force field forms, and fades away to reveal a blonde haired woman dressed in armor and carrying a sword. It’s Teela!
He-Man is overjoyed to see Teela again, as they fight the Mutants and talk about how it’s like ‘old times’. Teela also tells Skeletor that Eternia has been peaceful since he left. Skeletor transports himself and the Mutants away using another spell from the book, also taking Grot, who is still tangled up in the vines.
Master Sebrian tells Mara that the Encyclopedia of Evil should have been destroyed long ago, but they were never able to find the Books. Mara shows some jealousy towards Teela. Sebrian humorously notes this, and Mara denies it, before leaving. Outside, The Sorceress tells He-Man that she was the one who sent Teela to him, to help with his homesickness, but that she must be in Grot's garden when the dragon iris flower blooms, or she will not be able to return to Eternia.
Meanwhile, Skeletor’s earlier transportation spell has taken he and the Mutants, and Grot, to some strange dimension, which he cant seem to get out off. He tries another chant, but instead it changes Quakke and BH into weird looking creatures. ‘That was a great choice’ says Flogg sarcastically, to which Skeletor snaps ‘Everybody’s a critic!’. Meanwhile, Teela observes that He-Man doesn’t seem happy on Primus, and asks him to return to Eternia with her, He-Man says he is happy here, but has been homesick, and seeing her was just what he needed.
Skeletor finally gets out of the odd dimension, and Quakke hits his mace against the ground, inadvertently opening up a secret passageway to the Vaults of Zaktus. He-Man and Teela rush to stop Skeletor, but he has already found the Books, and uses them to tie He-Man and Teela up in energy chains.
Mara sneaks into the vaults, having followed them to the garden, and grabs He-Man's sword, she then throws it at the chains and sets both he and Teela free. They drop to the floor and battle the Mutants. During the battle, Quakke's mace slams into the ground, and the vaults begin to fall apart. The Books are knocked down by falling debris and begin burning in the fire, Skeletor rushes to try and save them, but it is too late. With no other option, he uses a spell to transport himself and the Mutants out of the Vaults, just as the book he is holding burns away. He-Man, Teela and Mara all leave just as the Vaults seal back up.
In the gardens, He-Man and Teela wait for the dragon iris to bloom, Grot is also there, happy to be back. Teela tells He-Man she wishes he could go back with her, and they say their goodbyes, neither of them truly wanting to. As Teela fades away, He-Man looks sadly at the space she has left behind. He-Man hands Mara a flower from the garden, and says ‘Let’s go home’ as they walk off together.