The movie begins with the Disney logo fading into its animated counterpart giving the viewer the sense of an actual film. Inside, Cinderella's mice friends Jaq and Gus race to a chamber where the Fairy Godmother is reading the story of Cinderella to the other mice. Much to their disappointment, Gus and Jaq arrive just as the Fairy Godmother that "Cinderella and the Prince lived Happily Ever After".
With the Fairy Godmother's help, the mice set off to make a new book to narrate what happens after the Happily Ever After, by stringing three segments of stories together into one narrative.
(Cinderella's story) Cinderella is put in charge of the royal banquet while the King and the Prince, but realizes she doesn't agree with the way that it's usually run, led by a sharp and snobbish woman named Prudence, who teaches her how to handle things. With the help of other characters, Cinderella convinces everyone in the palace that everyone in the kingdom, including the peasants, should be allowed to participate in the next royal banquet and not everything has to go with traditional ways. The next Step is for Cinderella for having to have good poise and posture by balancing books on her head. But things don't go well for Cinderella, but with the help of her mouse friend she realizes she has to be herself and decideds to throw the royal banquet her way.
The mice add Cinderella's story of her first day in the castle to the book as Jaq gets some magical help from the Fairy Godmother opening a bottle of ink. Proclaiming that he doesn't like ("even a little [of]") "that magic stuff," Gus reminds him of his last encounter with it. Looking to impress a female mouse Jaq allows the Fairy Godmother to tell his story.
(Jaq's story) One of Cinderella mouse friends, Jaq, thinks he's too small to help Cinderella in the palace like he did in the first movie. The Fairy Godmother shows up to help him out, and he wishes for her to turn him into a human so he can help out like everyone else. However, this does not stop Pom-Pom, the palace's snobby cat (who became the mice's new nemesis as soon as they moved to the palace along with Cinderella and becomes Lucifer's crush in the third segment) from chasing Jaq around (Pom-Pom thought Jaq in human form was worth approximately ten mice). Mistakenly taken for "Sir Hugh", after an incident with an elephant at a fair, he learns to be happy for who he is and Fairy Godmother changes him back to his mouse form. It is also made evident that Jaq is in love with another mouse named Mary and that Pom-Pom belongs to the same woman who was terrified of Jaq.
In a magic mishap, one of the mice spills magic dust onto the art supplies causing them to become animated. The supplies begin to wreak havoc on the nearly completed book until the Fairy Godmother puts a stop to it. As the mice survey the mess they reminisce how they've seen worse and Jaq tells them of the time Anastasia fell in love.
(Anastasia's story) Anastasia, Cinderella's younger stepsister, falls in love with a common baker, which her mother and older sister Drizella aren't too happy with. Her mother and Drizella still want her to marry a rich man, and convince her to forget about the baker and say that everything in the baker's shop is inferior; thus, Anastasia has to go against her mother for the first time. At the same time, Lucifer (who was believed to have died at the first film's end) starts chasing Cinderella's mice and Anastasia is kicked by a horse when she and the baker meet, causing her to be left in rags by getting bread all over herself and breaks in tears when she crashes into the baker's shop. However, Cinderella finds out about Anastasia's feelings and tries to push her and the baker together. During the process, Lucifer enters the palace and continues to chase Cinderella's mice, but during the chase, he falls in love with Pom Pom despite her disliking him. The mice help their old nemesis Lucifer fall in love with Pom Pom, that is, if Lucifer promises to stop chasing mice. When Lucifer and Pom Pom get together, Pom Pom goads Lucifer into breaking his promise and helping her catch the mice. In the ensuing chase, the mice push a bucket of water on Pom Pom, and she dumps Lucifer out of spite. The baker, meanwhile, asks Anastasia to the upcoming ball, which her mother and Drizella are very unhappy about and Drizella tells her mother that Anastasia's become a disaster, and that she (Drizella) and her mother will become the laughing stock of the entire town. Anastasia stays with the baker and falls in love.
With a sigh, the mice finish their book. They sing a reprise of "Bibbidi-Bobbidi-Boo" as they chase after Cinderella in an attempt to give her the book. When they catch up with her, she asks them what it is, and Gus tells her that it is a book about them all. Cinderella thinks it's wonderful, and asks if the mice would like to read it together to which the mice give a resounding "Yes!" They gather in front of the fire and Cinderella begins to read the book, "Once Upon a Time..."
- Jennifer Hale as Cinderella
- Christopher Daniel Barnes as Prince Charming
- Rob Paulsen as Jaq/Grand Duke/The Baker/Sir Hugh/Bert/Flower Vendor
- Corey Burton as Gus
- Holland Taylor as Prudence
- Frank Welker as Lucifer/Pom-Pom/Bruno
- Maurice LaMarche as Anastasia/ Fairy Godmother/Mary/Beatrice and Daphne
- Tress MacNeille as Drizella
- Jim Cummings as Lady Tremaine
- Andre Stojka as The King