The movie opens with Troubadour, a French-speaking turtle who loves songs, reminding a television-show narrator that he had promised Troubadour one of his songs would be used in the show that day.
The narrator silently breaks his promise and walks away from Troubadour. He does not look where he is going and falls in a hole in the floor as the show is about to begin. Consequently, Troubadour is ushered in to tell the audience the story at the last minute, and he chooses his comic book of The Three Musketeers.
"Our story begins in the gutter", he says, where Mickey Mouse, Donald Duck, Goofy, and Mickey's dog Pluto are street urchins, who, while being robbed by masked bandits (played by the Beagle Boys) and are saved by the Royal Musketeers, Athos, Aramis, Porthos and D'Artagnan. Afterward, Athos gives his hat to Mickey as a souvenir. The urchins are inspired to be great musketeers some day.
Years later, the three are working as janitors in the palace along with Hubie, Marina, Rocko, Petra, Beanie, Timmy, Pikatwo, Bonkers, Fawn and Buck, still dreaming of becoming musketeers, despite their flaws: Donald is a "coward" (who turns into a chicken whenever he is frightened), Goofy is a "doofus", and Mickey is "just too small", according to Captain Pete of the Royal Musketeers. This leaves the three downhearted. Hubie does not hesitate to remind them otherwise, retelling his story of how he travelled 3000 miles to save Marina. Rocko begins to wonder if he'll ever find the right woman.
Meanwhile, Minnie Mouse, princess of France, and her lady-in-waiting, Daisy Duck, are in a palace discussing Minnie's obsession with finding her "one true love". Daisy says that she must marry someone who is of royal blood, and Minnie insists that she cannot marry someone she does not love. Minnie says she will know that he is "the one" when he makes her laugh. Minnie then takes a walk in the palace garden and barely escapes with her life when the Beagle Boys attempt to drop a safe on her.
A female raven-haired duck named Splatter Phoenix rushes to tell her boss, Captain Pete, that the Beagles were not successful in dropping the safe on Minnie. Pete gets upset, because the assignment was to kidnap the princess and keep her "safe" before the opera The Pirates of Penzance, which is when he plans to take over the kingdom. (This is accompanied by a running gag: whenever Pete mentions the opera, a poster of the opera is shown, and an excerpt of the chorus of "With cat-like tread", from that opera, can be heard.) Just then, Pete's lieutenant, Clarabelle Cow, tells Pete that Princess Minnie requests his presence. Pete goes to the princess, who tells him angrily that she wants musketeer bodyguards. Pete, knowing that skilled musketeers would jeopardize his kidnap plans, appoints Mickey, Donald, and Goofy to protect her, knowing that they will be easy to get rid of. He then went to the janitor room, telling Mickey, Donald, Goofy that they passed his test and have what it takes to become musketeers. Hubie and his friends congratulate them, proudly.
When the three "musketeers" meet Princess Minnie after strangling a suit of armor, she instantly falls in love with Mickey. The boys are so caught up wanting to make a good first impression that when Daisy comes in with a tray of cheese for Minnie and they see the accompanying knife, they tackle Daisy, foolishly thinking her a villain.
While Minnie and Daisy, protected by Mickey, Donald, and Goofy, go on a journey. They are ambushed by the Beagle Boys. Splatter Phoenix faces Rocko who retorts 'I don't fight girls!' only to be pinned down, then thrown off.
Donald hides and is eventually thrown off the carriage along with Bonkers, and Goofy is easily defeated, leaving Mickey and Hubie to fight the intruders. Mickey is also defeated, leaving the heroes along stranded. Mickey encourages his friends not to lose hope and they rush to rescue Minnie and Daisy. At the entrance to a tall tower where they are unable to open the door, Goofy tells everyone to stand back so he can break down the door, but Bonkers sees a push sign on the door and opens it before he can stop, which sends Goofy rolling past the Beagle Boys and out of the tower. Outside, Goofy bounces off a tree, gets kicked by a cow and is thrown by a windmill back into the tower, and goes rolling past the Beagle Boys again, only to knock Hubie and his friends down the tower stairs. Mickey and Donald catch up along with Rocko (who wasn't bowled over by Goofy) and fight the Beagle Boys and Splatter (in which Donald runs off during the fight). When Mickey, Rocko and Goofy are trapped with the Beagle Boys and Splatter, Goofy sees his shape in the window behind them and gets the idea to do the same thing again with Mickey and they manage to knock the Beagles and Splatter out of the tower and rescue Minnie and Daisy. After Mickey unties Minnie and makes her laugh, the two fall in love as they return to Paris, with the others
Pete is furious that the Beagle Boys and Splatter Phoenix failed in their task and realizes that the three protagonists are more of a threat than he originally anticipated. He then plans to get rid of them one by one. Splatter, however is confused and worried, because murder was not part of her job. Pete explains to Splatter that things have changed, leaving her to wonder whether this is right.
While on night duty, Goofy, Hubie, Marina and Rocko are lured away from the palace by Clarabelle (who uses a shadow puppet of Mickey). The Beagle Boys appear before Donald, capture him, and Pete tries to do away with him, but he escapes and tells the whole story to Mickey, Pikatwo, Bonkers, Fawn and Buck (who don't believe him at first) before running off. Fawn, Buck, the bird kids and Pikatwo realise that the penguins are missing and go to find them, Leaving Bonkers and Mickey. The two are then captured by Pete and Splatter, who chains them up in a dungeon in Mont Saint-Michel that will flood when the tide comes in.
On the way to the Paris Opéra, Splatter tries to reason with Pete that killing isn't what she does, but Pete rejects. Splatter finally decides enough is enough and tries to stop him, but Pete leaves her stranded in the woods.
Meanwhile, Clarabelle is about to throw a chained up Goofy to his death off a bridge. Hubie, Marina and Rocko are also chained, watching in horror. Goofy flirts with Clarabelle, and wins her heart with his "numbskull charm." She pulls him up and they kiss, but the bridge they're on breaks. Everyone plummets towards the river, but land on Donald's boat instead and survived. Fawn, the bird kids, Pikatwo and Buck arrive at the same time. Marina asks how they found them and Buck explains they had gone to look for them in the palace and could see them from a window. Clarabelle tells Fawn that her husband is in trouble, as well as Mickey.
The group head for Mont Saint-Michel and they try to convince Donald that they have to save Mickey and Bonkers but he is too scared to try after seeing a scary face (seen when the lighting strikes) on the mountain. A denigrating song by Troubadour, however, makes him change his mind. Before they leave, Splatter Phoenix is spotted by the water's edge. She apologises for the trouble she has caused. Rocko tells her she doesn't have to live like a villain any more and invites her to help them.
Everyone gets to Mont Saint-Michel just in time by pulling the chain holding Mickey and Bonkers out of the wall. Bonkers is pulled out, unconscious. Luckily, Fawn uses Pikatwo as a defibrillator and brings him back to life. After another inspirational speech from Hubie, our heroes (along with Splatter) set off to rescue the Princess.
Outside the Paris Opéra, Minnie is captured by the Beagle Boys and the smallest one poses as her, announcing to the public that she is handing the crown over to a gleeful Pete. Our heroes arrive and battle Pete and the Beagle Boys onstage, finally defeating them and saving the Princess (though what became of the villains is unknown). Rocko welcomes Splatter Phoenix into the family, sparking a romance between the two. Mickey and Minnie finally declare their love for one another, as do the others. Mickey, Donald and Goofy are dubbed royal musketeers.