"Beauty and the Wildebeest" begins by introducing Herman, an ugly wildebeest, and his beautiful gazelle crush, Lara. At the start of the episode, Herman is approaching a water hole to get a drink of water, but his ugliness chases away the animals that are gathered around the pool, leaving him alone with Lara and her gazelle friends. Once the two realize that they are in the presence of such an ugly beast, Lara's friends laugh and mock him for his appearance until Lara tells them to leave Herman alone. She then asks Herman if he will attend her birthday party, and, ignoring the protests of her friends, he accepts the invitation.
Later that day, Herman accidentally rams into a tree and gets doused by a bowl of food that comes toppling from its branches. Alerted by the accident, Rafiki scrambles down his tree and asks Herman if he's all right. Still saddened by his encounter with Lara, Herman admits his problems to Rafiki and asks the baboon for help in impressing Lara at her birthday party. After examining Herman's condition, Rafiki agrees to do so.
For his first lesson, Rafiki decides to teach Herman about posture. To start the lesson, he instructs Herman to walk across a line of crocodiles and then return to him without falling. Despite successfully crossing the crocodiles, Herman stumbles back to the bank by plowing into Rafiki and knocking them both into a tree.
On his second attempt to tame Herman, Rafiki offers the wildebeest a special drink that will make his voice sound less grotesque. Though initially hesitant to try the drink, Herman takes a sip and finds that the potion works but makes his voice change every few seconds. A simple hit on the head with Rafiki's stick makes the sounds stop changing, and Herman is left with a stunning new voice.
For his third trick, Rafiki works his magic on Herman by fixing his teeth and horns, bathing him, and giving him a makeover. At last, Rafiki deems the wildebeest handsome and tilts a mirror to show Herman his stunning new look.
Meanwhile, the savanna celebrates Lara's birthday with a giant cake. As the festivities commence, a muscular gazelle named Mel pops out of the cake and attempts to serenade Lara with song, but she is disgusted and rejects his kiss. Just as Mel moves in for another attempt, Lara turns to find that Herman is at her party and handsomer than ever. Outraged at being outdone by a wildebeest, Mel challenges Herman to a fight in which they will run at each other full force and collide horns. Determined to win Lara's heart, Herman agrees.
As the two charge at each other, Herman suddenly realizes that he must be true to himself and dunks his head underwater, changing back into an ugly beast. Mel stops short at Herman's transformation and runs away, screeching. Despite his victory, Herman is sad that he is ugly again and begins to troop away with Rafiki until he is stopped by Lara, who admires him for his bravery. She then dunks her head underwater, revealing herself to be ugly as well, and the two share a romantic kiss.